N-ARY 트리의 깊이

주어진 n-항 트리 양수 노드 값을 포함하는 작업은 다음을 찾는 것입니다. 깊이 나무의.
메모: 안 n-항 트리 각 노드가 가질 수 있는 트리입니다. 영 또는 더 어린이 노드. 노드당 최대 2개의 자식을 갖는 이진 트리와는 달리 (왼쪽과 오른쪽) n-ary 트리는 다음을 허용합니다. 여러 지점 또는 각 노드의 하위 항목입니다.

예:

입력:

산출: 3
설명: 루트(노드 81)에서 리프까지의 가장 긴 경로는 81 -> 26 -> 95 또는 81 -> 26 -> 86이며 최대 깊이는 3입니다.
입력:

산출: 2
설명: 루트(노드 4)에서 모든 리프(노드 5 또는 7)까지의 가장 긴 경로는 2개의 순회 수준만 필요하므로 2입니다.
상태 목록

접근하다:

아이디어는 다음을 계산하는 것입니다. N-ary 트리의 깊이 재귀적으로 초기화하다 최대 깊이 0으로 설정한 다음 재귀적으로 계산합니다. 깊이 각 어린이마다 추적하고 가장 높은 깊이 마주쳤다. 마지막으로 추가 1 (현재 노드에 대한) 최대 깊이로 이동하고 다음을 반환합니다. 결과 . 이 접근 방식을 사용하면 다음을 찾을 수 있습니다. 가장 긴 경로 루트에서 임의의 리프 노드까지.

N-Ary 트리는 일반 트리처럼 순회할 수 있습니다. 주어진 노드의 모든 자식을 고려하고 모든 노드에서 해당 함수를 재귀적으로 호출하면 됩니다.

C++

// C++ Code to find the depth of an N-ary tree #include    using namespace std; class Node { public:  int data;  vector<Node*> children;  Node(int val) {  data = val;  } }; // Recursive function to calculate maximum depth int maxDepth(Node* root) {    // If the node is null depth is 0  if (!root) {  return 0;  }  int depth = 0;  // Recur for all children and find the maximum depth  for (auto child : root->children) {  depth = max(depth maxDepth(child));  }  // Add 1 to include the current node  // in the depth count  return depth + 1; } int main() {  // Representation of given N-ary tree  // 1  // / |   // 2 3 4  // /   // 5 6  Node* root = new Node(1);  root->children.push_back(new Node(2));  root->children.push_back(new Node(3));  root->children.push_back(new Node(4));  root->children[0]->children.push_back(new Node(5));  root->children[2]->children.push_back(new Node(6));  cout << maxDepth(root);  return 0; }

Java

// 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

# 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

// 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));

산출

시간 복잡도: O(n) 각 노드가 한 번 방문되므로 n은 N-진 트리의 총 노드 수입니다.
보조 공간: O(h) 여기서 h는 재귀 호출 스택 사용으로 인한 트리의 높이입니다.

퀴즈 만들기

TechCodeview

N-Ary 트리의 깊이