Adott egy n-áris fa pozitív csomópontértékeket tartalmaz a feladat, hogy megtaláljuk a mélység a fáról.
Jegyzet: An n-áris fa egy fa, ahol minden csomópont rendelkezhet nulla vagy több gyermek csomópontok. Ellentétben egy bináris fával, amelynek csomópontonként legfeljebb két gyermeke van (bal és jobb) az n-áris fa lehetővé teszi több ág vagy gyermekeket minden csomóponthoz.
Példák:
Bemenet:
Kimenet: 3
Magyarázat: A leghosszabb út a gyökértől (81-es csomópont) a levélig 81 -> 26 -> 95 vagy 81 -> 26 -> 86, ami 3-as maximális mélységet ad.Bemenet:
Kimenet: 2
Magyarázat: A leghosszabb út a gyökértől (4. csomópont) bármely levélig (5. vagy 7. csomópont) a 2, mivel csak két szintű bejárást igényel.aktuális dátum java-ban
Megközelítés:
Az ötlet az, hogy kiszámítsuk a N-ágú fa mélysége rekurzív módon inicializálja a maximális mélység mint 0, majd rekurzívan számítsa ki a mélység minden gyermek számára, és nyomon követheti a legnagyobb mélység találkozott. Végül add hozzá 1 a maximális mélységre (az aktuális csomóponthoz), és térjen vissza a eredmény . Ez a megközelítés biztosítja, hogy megtaláljuk a leghosszabb út a gyökértől a levél bármely csomópontjáig.
Az N-Ary fán ugyanúgy áthaladhatunk, mint egy normál fán. Csak figyelembe kell vennünk egy adott csomópont összes gyermekét, és minden csomóponton rekurzívan meg kell hívnunk ezt a függvényt.
C++// C++ Code to find the depth of an N-ary tree #include
// Java Code to find the depth of an N-ary tree import java.util.*; class Node { int data; List<Node> children; Node(int val) { data = val; children = new ArrayList<>(); } } // Recursive function to calculate // maximum depth class GfG { static int maxDepth(Node root) { // If the node is null depth is 0 if (root == null) { return 0; } int depth = 0; // Recur for all children and find // the maximum depth for (Node child : root.children) { depth = Math.max(depth maxDepth(child)); } // Add 1 to include the current node // in the depth count return depth + 1; } public static void main(String[] args) { // Representation of given N-ary tree // 1 // / | // 2 3 4 // / // 5 6 Node root = new Node(1); root.children.add(new Node(2)); root.children.add(new Node(3)); root.children.add(new Node(4)); root.children.get(0).children.add(new Node(5)); root.children.get(2).children.add(new Node(6)); System.out.println(maxDepth(root)); } }
# Python Code to find the depth # of an N-ary tree class Node: def __init__(self val): self.data = val self.children = [] # Recursive function to calculate # maximum depth def max_depth(root): # If the node is None depth is 0 if not root: return 0 depth = 0 # Recur for all children and # find the maximum depth for child in root.children: depth = max(depth max_depth(child)) # Add 1 to include the current # node in the depth count return depth + 1 if __name__ == '__main__': # Representation of given N-ary tree # 1 # / | # 2 3 4 # / # 5 6 root = Node(1) root.children.append(Node(2)) root.children.append(Node(3)) root.children.append(Node(4)) root.children[0].children.append(Node(5)) root.children[2].children.append(Node(6)) print(max_depth(root))
// C# Code to find the depth of an N-ary tree using System; using System.Collections.Generic; class Node { public int data; public List<Node> children; public Node(int val) { data = val; children = new List<Node>(); } } // Recursive function to calculate // maximum depth class GfG { static int MaxDepth(Node root) { // If the node is null depth is 0 if (root == null) { return 0; } int depth = 0; // Recur for all children and find the maximum depth foreach (Node child in root.children) { depth = Math.Max(depth MaxDepth(child)); } // Add 1 to include the current // node in the depth count return depth + 1; } static void Main(string[] args) { // Representation of given N-ary tree // 1 // / | // 2 3 4 // / // 5 6 Node root = new Node(1); root.children.Add(new Node(2)); root.children.Add(new Node(3)); root.children.Add(new Node(4)); root.children[0].children.Add(new Node(5)); root.children[2].children.Add(new Node(6)); Console.WriteLine(MaxDepth(root)); } }
// JavaScript Code to find the depth // of an N-ary tree class Node { constructor(val) { this.data = val; this.children = []; } } // Recursive function to calculate // maximum depth function maxDepth(root) { // If the node is null depth is 0 if (!root) { return 0; } let depth = 0; // Recur for all children and find // the maximum depth for (let child of root.children) { depth = Math.max(depth maxDepth(child)); } // Add 1 to include the current node // in the depth count return depth + 1; } // Representation of given N-ary tree // 1 // / | // 2 3 4 // / // 5 6 const root = new Node(1); root.children.push(new Node(2)); root.children.push(new Node(3)); root.children.push(new Node(4)); root.children[0].children.push(new Node(5)); root.children[2].children.push(new Node(6)); console.log(maxDepth(root));
Kimenet
3
Időbeli összetettség: O(n), mivel minden csomópontot egyszer meglátogatnak, ahol n az N-számú fa csomópontjainak teljes száma.
Kiegészítő tér: O(h) ahol h a fa magassága a rekurzív hívásverem használat miatt.