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