Paso a paso La ruta más corta desde el Node de origen hasta el Node de destino en un árbol binario

Posted on by Rudeus Greyrat

Dada una raíz de árbol binario y dos enteros startValue y destValue que denotan el Node inicial y final respectivamente. La tarea es encontrar la ruta más corta desde el Node inicial hasta el Node final e imprimir la ruta en la forma de las instrucciones que se dan a continuación. 

  1. Ir de un Node a su Node secundario izquierdo se indica con la letra ‘L’ .
  2. Ir de un Node a su Node secundario derecho se indica con la letra ‘R’ .
  3. Para navegar desde un Node a su Node principal , use la letra ‘U’ .

Ejemplos: 

Entrada: root = [5, 1, 2, 3, nulo, 6, 4], startValue = 3, destValue = 6

              5
          / \
       1 2
    / / \
  3 6 4

Salida: “UURL” 
Explicación: El camino más corto es: 3 → 1 → 5 → 2 → 6.

Entrada: root = [2, 1], startValue = 2, destValue = 1

            2
          /
       1

Salida: “L”
Explicación: El camino más corto es: 2 → 1.

 

Enfoque: La forma más sencilla de resolver este problema es utilizar el LCA (Ancestro común más bajo) de un árbol binario . Siga los pasos a continuación para resolver el problema dado. 

  • Aplique LCA para obtener una nueva raíz.
  • Obtenga la Ruta desde la nueva raíz hasta start y dest .
  • Concatene startPath y destPath, y asegúrese de reemplazar el carácter de startPath con ‘U’ .

A continuación se muestra la implementación del enfoque anterior. 

C++

// C++ program for above approach
#include <iostream>
using namespace std;
 
// Structure of Tree
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val2)
    {
        val = val2;
        left = NULL;
        right = NULL;
    }
};
 
// Function to find LCA of two nodes
TreeNode* lca(TreeNode* root,
              int startValue,
              int destValue)
{
 
    // Base Case
    if (!root)
        return NULL;
 
    if (root->val == startValue)
        return root;
    if (root->val == destValue)
        return root;
    auto l = lca(root->left,
                 startValue, destValue);
    auto r = lca(root->right,
                 startValue, destValue);
 
    if (l && r)
        return root;
 
    return l ? l : r;
}
bool getPath(TreeNode* root,
             int value,
             string& path)
{
 
    // Base Cases
    if (!root)
        return false;
    if (root->val == value)
        return true;
 
    path += 'L';
    auto res = getPath(root->left,
                       value, path);
    if (res)
        return true;
    path.pop_back();
    path += 'R';
    res = getPath(root->right,
                  value, path);
    if (res)
        return true;
    path.pop_back();
    return false;
}
 
// Function to get directions
string getDirections(TreeNode* root,
                     int startValue,
                     int destValue)
{
    // Find the LCA first
    root = lca(root, startValue, destValue);
 
    string p1, p2;
 
    // Get the path
    getPath(root, startValue, p1);
    getPath(root, destValue, p2);
    for (auto& c : p1)
        c = 'U';
 
    // Return the concatenation
    return p1 + p2;
}
 
// Driver Code
int main()
{
 
    /*
             5
           /    \
         1       2
        /       /  \
      3        6    4
 
   */
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(1);
    root->right = new TreeNode(2);
    root->left->left = new TreeNode(3);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(4);
 
    int startValue = 3;
    int endValue = 6;
 
    // Function Call
    string ans = getDirections(
      root, startValue, endValue);
 
    // Print answer
    cout << ans;
}

Python3

# Python program for above approach
 
# Structure of Tree
class TreeNode :
    def __init__(self, val2):
        self.val = val2;
        self.left = None;
        self.right = None;
 
# Function to find LCA of two nodes
def lca(root, startValue, destValue):
     
    # Base Case
    if (not root):
        return None;
 
    if (root.val == startValue):
        return root;
    if (root.val == destValue):
        return root;
    l = lca(root.left,
        startValue, destValue);
    r = lca(root.right,
        startValue, destValue);
 
    if (l and r):
        return root;
 
    return l if l else r;
 
def getPath(root, value, path) :
     
    # Base Cases
    if (not root):
        return False;
    if (root.val == value):
        return True;
 
    path.append('L');
    res = getPath(root.left, value, path);
    if (res):
        return True;
         
    path.pop();
    path.append('R');
    res = getPath(root.right, value, path);
                   
    if (res):
        return True;
         
    path.pop();
    return False;
 
 
# Function to get directions
def getDirections(root, startValue, destValue) :
     
    # Find the LCA first
    root = lca(root, startValue, destValue);
 
    p1 = []
    p2 = []
 
    # Get the path
    getPath(root, startValue, p1);
    getPath(root, destValue, p2);
    for i in range(len(p1)):
        p1[i] = 'U';
 
    # Return the concatenation
    s = ""
    for i in range(len(p1)):
        s += p1[i];
    for i in range(len(p2)):
        s += p2[i];
    return s;
 
# Driver Code
"""
         5
       /    \
     1       2
    /       /  \
  3        6    4
"""
 
root = TreeNode(5);
root.left = TreeNode(1);
root.right = TreeNode(2);
root.left.left = TreeNode(3);
root.right.left = TreeNode(6);
root.right.right = TreeNode(4);
 
startValue = 3;
endValue = 6;
 
# Function Call
ans = getDirections(root, startValue,
                        endValue);
 
# Print answer
print(ans)
 
# self code is contributed by Saurabh Jaiswal

Javascript

<script>
 
// JavaScript program for above approach
 
// Structure of Tree
class TreeNode
{
    constructor(val2)
    {
        this.val = val2;
        this.left = null;
        this.right = null;
    }
};
 
// Function to find LCA of two nodes
function lca(root, startValue, destValue)
{
     
    // Base Case
    if (!root)
        return null;
 
    if (root.val == startValue)
        return root;
    if (root.val == destValue)
        return root;
    let l = lca(root.left,
        startValue, destValue);
    let r = lca(root.right,
        startValue, destValue);
 
    if (l && r)
        return root;
 
    return l ? l : r;
}
 
function getPath(root, value, path)
{
     
    // Base Cases
    if (!root)
        return false;
    if (root.val == value)
        return true;
 
    path.push('L');
    let res = getPath(root.left,
                      value, path);
    if (res)
        return true;
         
    path.pop();
    path.push('R');
    res = getPath(root.right,
                  value, path);
                   
    if (res)
        return true;
         
    path.pop();
    return false;
}
 
// Function to get directions
function getDirections(root, startValue,
                       destValue)
{
     
    // Find the LCA first
    root = lca(root, startValue, destValue);
 
    let p1 = [], p2 = [];
 
    // Get the path
    getPath(root, startValue, p1);
    getPath(root, destValue, p2);
    for(let i = 0; i < p1.length; i++)
        p1[i] = 'U';
 
    // Return the concatenation
    let s = ""
    for(let i = 0; i < p1.length; i++)
    {
        s += p1[i];
    }
    for(let i = 0; i < p2.length; i++)
    {
        s += p2[i];
    }
    return s;
}
 
// Driver Code
/*
         5
       /    \
     1       2
    /       /  \
  3        6    4
 
*/
let root = new TreeNode(5);
root.left = new TreeNode(1);
root.right = new TreeNode(2);
root.left.left = new TreeNode(3);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(4);
 
let startValue = 3;
let endValue = 6;
 
// Function Call
let ans = getDirections(root, startValue,
                        endValue);
 
// Print answer
document.write(ans)
 
// This code is contributed by Potta Lokesh
 
</script>
Producción

UURL

Complejidad temporal: O(3N), porque se realizan tres recorridos.
Espacio Auxiliar: O(1)

Enfoque eficiente: este enfoque se basa en la implementación, pero no se utiliza LCA en este enfoque. Siga los pasos a continuación para resolver el problema dado.  

  • Cree indicaciones tanto para el inicio como para el destino desde la raíz.
  • Digamos que obtenemos «LLRRL» y «LRR» .
  • Eliminar ruta de prefijo común.
  • Eliminamos «L» , y ahora la dirección de inicio es «LRRL» , y el destino – «RR»
  • Reemplace todos los pasos en la dirección de inicio a «U» y agregue la dirección de destino.
  • El resultado es “UUUU” + “RR” .

A continuación se muestra la implementación del enfoque anterior.  

C++

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Structure of Tree
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val2)
    {
        val = val2;
        left = NULL;
        right = NULL;
    }
};
 
// Find Function
bool find(TreeNode* n, int val,
          string& path)
{
    if (n->val == val)
        return true;
    if (n->left && find(n->left,
                        val, path)) {
        path.push_back('L');
        return true;
    }
    if (n->right && find(n->right,
                         val, path)) {
        path.push_back('R');
        return true;
    }
    return false;
}
 
// Function to keep track
// of directions at any point
string getDirections(TreeNode* root,
                     int startValue,
                     int destValue)
{
 
    // To store the startPath and destPath
    string s_p, d_p;
    find(root, startValue, s_p);
    find(root, destValue, d_p);
 
    while (!s_p.empty() && !d_p.empty()
           && s_p.back() == d_p.back()) {
        s_p.pop_back();
        d_p.pop_back();
    }
 
    for (int i = 0; i < s_p.size(); i++) {
        s_p[i] = 'U';
    }
    reverse(d_p.begin(), d_p.end());
    string ans = s_p + d_p;
    return ans;
}
 
// Driver Code
int main()
{
 
    /*
             5
           /    \
         1       2
        /       /  \
      3        6    4
 
 
   */
 
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(1);
    root->right = new TreeNode(2);
    root->left->left = new TreeNode(3);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(4);
 
    int startValue = 3;
    int endValue = 6;
 
    // Function Call
    string ans = getDirections(
      root, startValue, endValue);
 
    // Print the result
    cout << ans;
}
Producción

UURL

Complejidad de tiempo: O(N)
Espacio auxiliar: O(1), si se descuida el espacio de la pila de recursividad. 

Publicación traducida automáticamente

Artículo escrito por rishabhbatra53 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *