Imprima todas las rutas de raíz a hoja de un árbol N-ario

Posted on by Rudeus Greyrat

Dado un árbol N-ario , la tarea es imprimir todas las rutas de la raíz a la hoja del árbol N-ario dado .

Ejemplos:

Entrada:
                        1
                      / \
                   2 3
                 / / \
              4 5 6
                           / \
                        7 8

Salida:
1 2 4
1 3 5
1 3 6 7
1 3 6 8

Entrada:
                          1
                        / | \
                      2 5 3
                    / \ \
                   4 5 6
Salida:
1 2 4
1 2 5
1 5
1 3 6

Enfoque: La idea para resolver este problema es comenzar a atravesar el árbol N-ario usando la búsqueda primero en profundidad y seguir insertando cada Node encontrado en un vector hasta que se encuentre un Node hoja . Cada vez que se encuentre un Node de hoja, imprima los elementos almacenados en el vector como la ruta actual de raíz a hoja atravesada y elimine la última hoja agregada y verifique la siguiente combinación.

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Structure of an N ary tree node
class Node {
public:
    int data;
    vector<Node*> child;
 
    // Parameterized Constructor
    Node(int x)
        : data(x)
    {
    }
};
 
// Function to print the root to leaf
// path of the given N-ary Tree
void printPath(vector<int> vec)
{
    // Print elements in the vector
    for (int ele : vec) {
        cout << ele << " ";
    }
    cout << endl;
}
 
// Utility function to print all
// root to leaf paths of an Nary Tree
void printAllRootToLeafPaths(
    Node* root, vector<int> vec)
{
    // If root is null
    if (!root)
        return;
 
    // Insert current node's
    // data into the vector
    vec.push_back(root->data);
 
    // If current node is a leaf node
    if (root->child.empty()) {
 
        // Print the path
        printPath(vec);
 
        // Pop the leaf node
        // and return
        vec.pop_back();
        return;
    }
 
    // Recur for all children of
    // the current node
    for (int i = 0;
        i < root->child.size(); i++)
 
        // Recursive Function Call
        printAllRootToLeafPaths(
            root->child[i], vec);
}
 
// Function to print root to leaf path
void printAllRootToLeafPaths(Node* root)
{
    // If root is null, return
    if (!root)
        return;
 
    // Stores the root to leaf path
    vector<int> vec;
 
    // Utility function call
    printAllRootToLeafPaths(root, vec);
}
 
// Driver Code
int main()
{
    // Given N-Ary tree
    Node* root = new Node(1);
    (root->child).push_back(new Node(2));
    (root->child).push_back(new Node(3));
    (root->child[0]->child).push_back(new Node(4));
    (root->child[1]->child).push_back(new Node(5));
    (root->child[1]->child).push_back(new Node(6));
    (root->child[1]->child[1]->child)
        .push_back(new Node(7));
    (root->child[1]->child[1]->child)
        .push_back(new Node(8));
 
    // Function Call
    printAllRootToLeafPaths(root);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.ArrayList;
class GFG
{
 
    // Structure of an N ary tree node
    static class Node
    {
        int data;
        ArrayList<Node> child;
 
        // Parameterized Constructor
        public Node(int x)
        {
            this.data = x;
            this.child = new ArrayList<>();
        }
    };
 
    // Function to print the root to leaf
    // path of the given N-ary Tree
    static void printPath(ArrayList<Integer> vec)
    {
       
        // Print elements in the vector
        for (int ele : vec)
        {
            System.out.print(ele + " ");
        }
        System.out.println();
    }
 
    // Utility function to print all
    // root to leaf paths of an Nary Tree
    static void printAllRootToLeafPaths(Node root, ArrayList<Integer> vec)
    {
       
        // If root is null
        if (root == null)
            return;
 
        // Insert current node's
        // data into the vector
        vec.add(root.data);
 
        // If current node is a leaf node
        if (root.child.isEmpty())
        {
 
            // Print the path
            printPath(vec);
 
            // Pop the leaf node
            // and return
            vec.remove(vec.size() - 1);
            return;
        }
 
        // Recur for all children of
        // the current node
        for (int i = 0; i < root.child.size(); i++)
 
            // Recursive Function Call
            printAllRootToLeafPaths(root.child.get(i), vec);
        vec.remove(vec.size() - 1);
    }
 
    // Function to print root to leaf path
    static void printAllRootToLeafPaths(Node root)
    {
       
        // If root is null, return
        if (root == null)
            return;
 
        // Stores the root to leaf path
        ArrayList<Integer> vec = new ArrayList<>();
 
        // Utility function call
        printAllRootToLeafPaths(root, vec);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        // Given N-Ary tree
        Node root = new Node(1);
        (root.child).add(new Node(2));
        (root.child).add(new Node(3));
        (root.child.get(0).child).add(new Node(4));
        (root.child.get(1).child).add(new Node(5));
        (root.child.get(1).child).add(new Node(6));
        (root.child.get(1).child.get(1).child).add(new Node(7));
        (root.child.get(1).child.get(1).child).add(new Node(8));
 
        // Function Call
        printAllRootToLeafPaths(root);
    }
}
 
// This code is contributed by sanjeev2552

Python3

# Python3 program for the above approach
 
# Structure of an N ary tree node
class Node:
     
    def __init__(self, x):
         
        self.data = x
        self.child = []
 
# Function to print the root to leaf
# path of the given N-ary Tree
def printPath(vec):
     
    # Print elements in the vector
    for ele in vec:
        print(ele, end = " ")
         
    print()
 
# Utility function to print all
# root to leaf paths of an Nary Tree
def printAllRootToLeafPaths(root):
     
    global vec
     
    # If root is null
    if (not root):
        return
 
    # Insert current node's
    # data into the vector
    vec.append(root.data)
 
    # If current node is a leaf node
    if (len(root.child) == 0):
 
        # Print the path
        printPath(vec)
 
        # Pop the leaf node
        # and return
        vec.pop()
        return
 
    # Recur for all children of
    # the current node
    for i in range(len(root.child)):
 
        # Recursive Function Call
        printAllRootToLeafPaths(root.child[i])
         
    vec.pop()   
 
# Function to print root to leaf path
def printRootToLeafPaths(root):
     
    global vec
     
    # If root is null, return
    if (not root):
        return
 
    # Utility function call
    printAllRootToLeafPaths(root)
 
# Driver Code
if __name__ == '__main__':
     
    # Given N-Ary tree
    vec = []
    root = Node(1)
    root.child.append(Node(2))
    root.child.append(Node(3))
    root.child[0].child.append(Node(4))
    root.child[1].child.append(Node(5))
    root.child[1].child.append(Node(6))
    root.child[1].child[1].child.append(Node(7))
    root.child[1].child[1].child.append(Node(8))
 
    # Function Call
    printRootToLeafPaths(root)
 
# This code is contributed by mohit kumar 29

C#

using System;
using System.Collections.Generic;
 
// Structure of an N ary tree node
public class Node
{
    public int data;
    public List<Node> child;
  
    // Parameterized Constructor
    public Node(int x)
    {
        this.data = x;
        this.child = new List<Node>();
    }
}
 
public class GFG
{
     
    // Function to print the root to leaf
    // path of the given N-ary Tree
    static void printPath(List<int> vec)
    {
        
        // Print elements in the vector
        foreach (int ele in vec)
        {
            Console.Write(ele + " ");
        }
        Console.WriteLine();
    }
     
    // Utility function to print all
    // root to leaf paths of an Nary Tree
    static void printAllRootToLeafPaths(Node root, List<int> vec)
    {
       
        // If root is null
        if (root == null)
            return;
  
        // Insert current node's
        // data into the vector
        vec.Add(root.data);
         
        // If current node is a leaf node
        if (root.child.Count == 0)
        {
           
            // Print the path
            printPath(vec);
  
            // Pop the leaf node
            // and return
            vec.RemoveAt(vec.Count - 1);
            return;
        }
         
        // Recur for all children of
        // the current node
        for (int i = 0; i < root.child.Count; i++)
        {
            // Recursive Function Call
            printAllRootToLeafPaths(root.child[i], vec);
        }
        vec.RemoveAt(vec.Count - 1);
    }
     
    // Function to print root to leaf path
    static void printAllRootToLeafPaths(Node root)
    {
        
        // If root is null, return
        if (root == null)
            return;
  
        // Stores the root to leaf path
        List<int> vec = new List<int>();
  
        // Utility function call
        printAllRootToLeafPaths(root, vec);
    }
     
    // Driver Code
    static public void Main ()
    {
       
        // Given N-Ary tree
        Node root = new Node(1);
        (root.child).Add(new Node(2));
        (root.child).Add(new Node(3));
        (root.child[0].child).Add(new Node(4));
        (root.child[1].child).Add(new Node(5));
        (root.child[1].child).Add(new Node(6));
        (root.child[1].child[1].child).Add(new Node(7));
        (root.child[1].child[1].child).Add(new Node(8));
         
        // Function Call
        printAllRootToLeafPaths(root);
    }
}
 
// This code is contributed by rag2127

Javascript

<script>
// Javascript program for the above approach
 
// Structure of an N ary tree node
class Node
{
    constructor(x)
    {
        this.data = x;
            this.child = [];
    }
}
 
// Function to print the root to leaf
    // path of the given N-ary Tree
function  printPath(vec)
{
    // Print elements in the vector
        for (let ele=0;ele< vec.length;ele++)
        {
            document.write(vec[ele] + " ");
        }
        document.write("<br>");
}
 
// Utility function to print all
    // root to leaf paths of an Nary Tree
function printAllRootToLeafPaths(root,vec)
{
    // If root is null
        if (root == null)
            return;
  
        // Insert current node's
        // data into the vector
        vec.push(root.data);
  
        // If current node is a leaf node
        if (root.child.length==0)
        {
  
            // Print the path
            printPath(vec);
  
            // Pop the leaf node
            // and return
            vec.pop();
            return;
        }
  
        // Recur for all children of
        // the current node
        for (let i = 0; i < root.child.length; i++)
  
            // Recursive Function Call
            printAllRootToLeafPaths(root.child[i], vec);
        vec.pop();
}
 
// Function to print root to leaf path
function printAllRootToLeaf_Paths(root)
{
    // If root is null, return
        if (root == null)
            return;
  
        // Stores the root to leaf path
        let vec = [];
  
        // Utility function call
        printAllRootToLeafPaths(root, vec);
}
 
// Driver Code
let root = new Node(1);
(root.child).push(new Node(2));
(root.child).push(new Node(3));
(root.child[0].child).push(new Node(4));
(root.child[1].child).push(new Node(5));
(root.child[1].child).push(new Node(6));
(root.child[1].child[1].child).push(new Node(7));
(root.child[1].child[1].child).push(new Node(8));
 
// Function Call
printAllRootToLeaf_Paths(root);
 
// This code is contributed by unknown2108
</script>
Producción: 

1 2 4 
1 3 5 
1 3 6 7 
1 3 6 8

 

Complejidad temporal: O(N)
Complejidad espacial: O(N)

Publicación traducida automáticamente

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