Gegeven een n-aire boom met positieve knooppuntwaarden is het de taak om de diepte van de boom.
Opmerking: Een n-aire boom is een boom waarin elk knooppunt kan hebben nul of meer kinderen knooppunten. In tegenstelling tot een binaire boom die maximaal twee kinderen per knooppunt heeft (links en rechts) de n-aire boom maakt dit mogelijk meerdere vestigingen of kinderen voor elk knooppunt.
Voorbeelden:
Invoer:
Uitgang: 3
Uitleg: Het langste pad van de wortel (knooppunt 81) naar een blad is 81 -> 26 -> 95 of 81 -> 26 -> 86, wat een maximale diepte van 3 oplevert.Invoer:
Uitgang: 2
Uitleg: Het langste pad van de wortel (knooppunt 4) naar een blad (knooppunt 5 of 7) is 2, omdat er slechts twee doorgangsniveaus nodig zijn.java vervang teken in string
Benadering:
Het idee is om de diepte van een N-ary boom recursief initialiseer de maximale diepte als 0 en bereken vervolgens recursief de diepte voor elk kind en houd de gegevens bij hoogste diepte tegengekomen. Tenslotte toevoegen 1 naar de maximale diepte (voor het huidige knooppunt) en retourneer de resultaat . Deze aanpak zorgt ervoor dat we de langste pad van de wortel tot elk bladknooppunt.
De N-Ary-boom kan net als een normale boom worden doorkruist. We hoeven alleen maar rekening te houden met alle kinderen van een bepaald knooppunt en die functie recursief op elk knooppunt aan te roepen.
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));
Uitvoer
3
Tijdcomplexiteit: O(n) aangezien elk knooppunt één keer wordt bezocht, waarbij n het totale aantal knooppunten in de N-aire boom is.
Hulpruimte: O(h) waarbij h de hoogte van de boom is als gevolg van recursief gebruik van de call-stack.