Imprima la primera ruta más corta de raíz a hoja en un árbol binario

Dado un árbol binario con valores distintos, la tarea es imprimir la primera ruta más pequeña de raíz a hoja. Básicamente, necesitamos imprimir la ruta de raíz a hoja más a la izquierda que tenga la cantidad mínima de Nodes.

Input:
          1
         /  \
        2    3
       /    / \
      4    5   7
     / \        \
    10  11       8
Output: 1 3 5


Input:
          1
         /  \
        2    3
       /    / \
      40   5   7
                \
                 8
Output: 1 2 40

Enfoque: la idea es usar una cola para realizar un recorrido de orden de nivel , un mapa principal para almacenar los Nodes que estarán presentes en la ruta más corta. Usando el recorrido de orden de nivel, encontramos la hoja más a la izquierda. Una vez que encontramos la hoja más a la izquierda, imprimimos la ruta usando el mapa.

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

C++

// C++ program to print first shortest
// root to leaf path
#include <bits/stdc++.h>
using namespace std;
 
// Binary tree node
struct Node {
    struct Node* left;
    struct Node* right;
    int data;
};
 
// Function to create a new
// Binary node
struct Node* newNode(int data)
{
    struct Node* temp = new Node;
 
    temp->data = data;
    temp->left = NULL;
    temp->right = NULL;
 
    return temp;
}
 
// Recursive function used by leftMostShortest
// to print the first shortest root to leaf path
void printPath(int Data, unordered_map<int,
                             int> parent)
{
    // If the root's data is same as
    // its parent data then return
    if (parent[Data] == Data)
        return;
 
    // Recur for the function printPath
    printPath(parent[Data], parent);
 
    // Print the parent node's data
    cout << parent[Data] << " ";
}
 
// Function to perform level order traversal
// until we find the first leaf node
void leftMostShortest(struct Node* root)
{
    // Queue to store the nodes
    queue<struct Node*> q;
 
    // Push the root node
    q.push(root);
 
    // Initialize the value of first
    // leaf node to occur as -1
    int LeafData = -1;
 
    // To store the current node
    struct Node* temp = NULL;
 
    // Map to store the parent node's data
    unordered_map<int, int> parent;
 
    // Parent of root data is set as it's
    // own value
    parent[root->data] = root->data;
 
    // We store first node of the smallest level
    while (!q.empty()) {
        temp = q.front();
        q.pop();
 
        // If the first leaf node has been found
        // set the flag variable as 1
        if (!temp->left && !temp->right) {
            LeafData = temp->data;
            break;
        }
        else {
 
            // If current node has left
            // child, push in the queue
            if (temp->left) {
                q.push(temp->left);
 
                // Set temp's left node's parent as temp
                parent[temp->left->data] = temp->data;
            }
 
            // If current node has right
            // child, push in the queue
            if (temp->right) {
                q.push(temp->right);
 
                // Set temp's right node's parent
                // as temp
                parent[temp->right->data] = temp->data;
            }
        }
    }
 
    // Recursive function to print the first
    // shortest root to leaf path
    printPath(LeafData, parent);
 
    // Print the leaf node of the first
    // shortest path
    cout << LeafData << " ";
}
 
// Driver code
int main()
{
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->right->left = newNode(5);
    root->right->right = newNode(7);
    root->left->left->left = newNode(10);
    root->left->left->right = newNode(11);
    root->right->right->left = newNode(8);
 
    leftMostShortest(root);
 
    return 0;
}

Java

// Java program to print first shortest
// root to leaf path
import java.util.*;
 
class GFG{
 
// Binary tree node
static class Node
{
    Node left;
    Node right;
    int data;
};
 
// Function to create a new
// Binary node
static Node newNode(int data)
{
    Node temp = new Node();
 
    temp.data = data;
    temp.left = null;
    temp.right = null;
 
    return temp;
}
 
// Recursive function used by leftMostShortest
// to print the first shortest root to leaf path
static void printPath(int Data,
                      HashMap<Integer,
                              Integer> parent)
{
     
    // If the root's data is same as
    // its parent data then return
    if (parent.get(Data) == Data)
        return;
 
    // Recur for the function printPath
    printPath(parent.get(Data), parent);
 
    // Print the parent node's data
    System.out.print(parent.get(Data) + " ");
}
 
// Function to perform level order traversal
// until we find the first leaf node
static void leftMostShortest(Node root)
{
     
    // Queue to store the nodes
    Queue<Node> q = new LinkedList<>();
 
    // Add the root node
    q.add(root);
 
    // Initialize the value of first
    // leaf node to occur as -1
    int LeafData = -1;
 
    // To store the current node
    Node temp = null;
 
    // Map to store the parent node's data
    HashMap<Integer,
            Integer> parent = new HashMap<>();
 
    // Parent of root data is set as it's
    // own value
    parent.put(root.data, root.data);
 
    // We store first node of the smallest level
    while (!q.isEmpty())
    {
        temp = q.poll();
 
        // If the first leaf node has been found
        // set the flag variable as 1
        if (temp.left == null &&
            temp.right == null)
        {
            LeafData = temp.data;
            break;
        }
        else
        {
 
            // If current node has left
            // child, add in the queue
            if (temp.left != null)
            {
                q.add(temp.left);
 
                // Set temp's left node's parent
                // as temp
                parent.put(temp.left.data,
                           temp.data);
            }
 
            // If current node has right
            // child, add in the queue
            if (temp.right != null)
            {
                q.add(temp.right);
 
                // Set temp's right node's parent
                // as temp
                parent.put(temp.right.data,
                                 temp.data);
            }
        }
    }
 
    // Recursive function to print the
    // first shortest root to leaf path
    printPath(LeafData, parent);
 
    // Print the leaf node of the first
    // shortest path
    System.out.println(LeafData + " ");
}
 
// Driver Code
public static void main(String[] args)
{
    Node root = newNode(1);
    root.left = newNode(2);
    root.right = newNode(3);
    root.left.left = newNode(4);
    root.right.left = newNode(5);
    root.right.right = newNode(7);
    root.left.left.left = newNode(10);
    root.left.left.right = newNode(11);
    root.right.right.left = newNode(8);
 
    leftMostShortest(root);
}
}
 
// This code is contributed by sanjeev2552

Python3

# Python3 program to print first
# shortest root to leaf path
 
# Binary tree node
class Node:
     
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# Recursive function used by leftMostShortest
# to print the first shortest root to leaf path
def printPath(Data, parent):
 
    # If the root's data is same as
    # its parent data then return
    if parent[Data] == Data:
        return
 
    # Recur for the function printPath
    printPath(parent[Data], parent)
 
    # Print the parent node's data
    print(parent[Data], end = " ")
 
# Function to perform level order traversal
# until we find the first leaf node
def leftMostShortest(root):
 
    # Queue to store the nodes
    q = []
 
    # Push the root node
    q.append(root)
 
    # Initialize the value of first
    # leaf node to occur as -1
    LeafData = -1
 
    # To store the current node
    temp = None
 
    # Map to store the parent node's data
    parent = {}
 
    # Parent of root data is set
    # as it's own value
    parent[root.data] = root.data
 
    # We store first node of the
    # smallest level
    while len(q) != 0:
        temp = q.pop(0)
 
        # If the first leaf node has been
        # found set the flag variable as 1
        if not temp.left and not temp.right:
            LeafData = temp.data
            break
         
        else:
             
            # If current node has left
            # child, push in the queue
            if temp.left:
                q.append(temp.left)
 
                # Set temp's left node's parent as temp
                parent[temp.left.data] = temp.data
 
            # If current node has right
            # child, push in the queue
            if temp.right:
                q.append(temp.right)
 
                # Set temp's right node's parent
                # as temp
                parent[temp.right.data] = temp.data
 
    # Recursive function to print the first
    # shortest root to leaf path
    printPath(LeafData, parent)
 
    # Print the leaf node of the
    # first shortest path
    print(LeafData, end = " ")
 
# Driver code
if __name__ == "__main__":
 
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.right.left = Node(5)
    root.right.right = Node(7)
    root.left.left.left = Node(10)
    root.left.left.right = Node(11)
    root.right.right.left = Node(8)
 
    leftMostShortest(root)
 
# This code is contributed by Rituraj Jain

C#

// C# program to print first shortest
// root to leaf path
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG{
  
// Binary tree node
public class Node
{
    public Node left;
    public Node right;
    public int data;
};
  
// Function to create a new
// Binary node
public static Node newNode(int data)
{
    Node temp = new Node();
  
    temp.data = data;
    temp.left = null;
    temp.right = null;
  
    return temp;
}
  
// Recursive function used by leftMostShortest
// to print the first shortest root to leaf path
static void printPath(int Data,
           Dictionary<int, int> parent)
{
      
    // If the root's data is same as
    // its parent data then return
    if (parent[Data] == Data)
        return;
  
    // Recur for the function printPath
    printPath(parent[Data], parent);
  
    // Print the parent node's data
    Console.Write(parent[Data] + " ");
}
  
// Function to perform level order traversal
// until we find the first leaf node
static void leftMostShortest(Node root)
{
      
    // Queue to store the nodes
    Queue q = new Queue();
  
    // Add the root node
    q.Enqueue(root);
  
    // Initialize the value of first
    // leaf node to occur as -1
    int LeafData = -1;
  
    // To store the current node
    Node temp = null;
  
    // Map to store the parent node's data
    Dictionary<int,
               int> parent = new Dictionary<int,
                                            int>();
  
    // Parent of root data is set as it's
    // own value
    parent[root.data] = root.data;
  
    // We store first node of the
    // smallest level
    while (q.Count != 0)
    {
        temp = (Node)q.Dequeue();
  
        // If the first leaf node has been
        // found set the flag variable as 1
        if (temp.left == null &&
           temp.right == null)
        {
            LeafData = temp.data;
            break;
        }
        else
        {
  
            // If current node has left
            // child, add in the queue
            if (temp.left != null)
            {
                q.Enqueue(temp.left);
  
                // Set temp's left node's parent
                // as temp
                parent[temp.left.data] = temp.data;
            }
  
            // If current node has right
            // child, add in the queue
            if (temp.right != null)
            {
                q.Enqueue(temp.right);
  
                // Set temp's right node's parent
                // as temp
                parent[temp.right.data] = temp.data;
            }
        }
    }
  
    // Recursive function to print the
    // first shortest root to leaf path
    printPath(LeafData, parent);
  
    // Print the leaf node of the first
    // shortest path
    Console.Write(LeafData + " ");
}
  
// Driver Code
public static void Main(string[] args)
{
    Node root = newNode(1);
    root.left = newNode(2);
    root.right = newNode(3);
    root.left.left = newNode(4);
    root.right.left = newNode(5);
    root.right.right = newNode(7);
    root.left.left.left = newNode(10);
    root.left.left.right = newNode(11);
    root.right.right.left = newNode(8);
  
    leftMostShortest(root);
}
}
 
// This code is contributed by rutvik_56

Javascript

<script>
 
    // JavaScript program to print first
    // shortest root to leaf path
     
    // Binary tree node
    class Node
    {
        constructor(data) {
           this.left = null;
           this.right = null;
           this.data = data;
        }
    }
     
    // Function to create a new
    // Binary node
    function newNode(data)
    {
        let temp = new Node(data);
        return temp;
    }
 
    // Recursive function used by leftMostShortest
    // to print the first shortest root to leaf path
    function printPath(Data, parent)
    {
 
        // If the root's data is same as
        // its parent data then return
        if (parent.get(Data) == Data)
            return;
 
        // Recur for the function printPath
        printPath(parent.get(Data), parent);
 
        // Print the parent node's data
        document.write(parent.get(Data) + " ");
    }
 
    // Function to perform level order traversal
    // until we find the first leaf node
    function leftMostShortest(root)
    {
 
        // Queue to store the nodes
        let q = [];
 
        // Add the root node
        q.push(root);
 
        // Initialize the value of first
        // leaf node to occur as -1
        let LeafData = -1;
 
        // To store the current node
        let temp = null;
 
        // Map to store the parent node's data
        let parent = new Map();
 
        // Parent of root data is set as it's
        // own value
        parent.set(root.data, root.data);
 
        // We store first node of the smallest level
        while (q.length > 0)
        {
            temp = q[0];
            q.shift();
 
            // If the first leaf node has been found
            // set the flag variable as 1
            if (temp.left == null &&
                temp.right == null)
            {
                LeafData = temp.data;
                break;
            }
            else
            {
 
                // If current node has left
                // child, add in the queue
                if (temp.left != null)
                {
                    q.push(temp.left);
 
                    // Set temp's left node's parent
                    // as temp
                    parent.set(temp.left.data,
                               temp.data);
                }
 
                // If current node has right
                // child, add in the queue
                if (temp.right != null)
                {
                    q.push(temp.right);
 
                    // Set temp's right node's parent
                    // as temp
                    parent.set(temp.right.data,
                                     temp.data);
                }
            }
        }
 
        // Recursive function to print the
        // first shortest root to leaf path
        printPath(LeafData, parent);
 
        // Print the leaf node of the first
        // shortest path
        document.write(LeafData + " ");
    }
     
    let root = newNode(1);
    root.left = newNode(2);
    root.right = newNode(3);
    root.left.left = newNode(4);
    root.right.left = newNode(5);
    root.right.right = newNode(7);
    root.left.left.left = newNode(10);
    root.left.left.right = newNode(11);
    root.right.right.left = newNode(8);
  
    leftMostShortest(root);
 
</script>
Producción: 

1 3 5

 

Complejidad temporal : O(N) 
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por Sakshi_Srivastava 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 *