原题链接在这里:https://leetcode.com/problems/maximum-depth-of-n-ary-tree/description/
题目:
Given a n-ary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).
Example 1:
Input: root = [1,null,3,2,4,null,5,6] Output: 3
Example 2:
Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] Output: 5
Constraints:
- The total number of nodes is in the range
[0, 104]
. - The depth of the n-ary tree is less than or equal to
1000
.
题解:
Find the maxmimum depth among each subtree and return max + 1.
Time Complexity: O(n).
Space: O(h).
AC Java:
1 /* 2 // Definition for a Node. 3 class Node { 4 public int val; 5 public List<Node> children; 6 7 public Node() {} 8 9 public Node(int _val) { 10 val = _val; 11 } 12 13 public Node(int _val, List<Node> _children) { 14 val = _val; 15 children = _children; 16 } 17 }; 18 */ 19 20 class Solution { 21 public int maxDepth(Node root) { 22 if(root == null){ 23 return 0; 24 } 25 26 int depth = 0; 27 for(Node next : root.children){ 28 depth = Math.max(depth, maxDepth(next)); 29 } 30 31 return depth + 1; 32 } 33 }
AC C++:
1 /* 2 // Definition for a Node. 3 class Node { 4 public: 5 int val; 6 vector<Node*> children; 7 8 Node() {} 9 10 Node(int _val) { 11 val = _val; 12 } 13 14 Node(int _val, vector<Node*> _children) { 15 val = _val; 16 children = _children; 17 } 18 }; 19 */ 20 21 class Solution { 22 public: 23 int maxDepth(Node* root) { 24 if(!root){ 25 return 0; 26 } 27 28 int depth = 0; 29 for(Node* next : root->children){ 30 depth = max(depth, maxDepth(next)); 31 } 32 33 return depth + 1; 34 } 35 };
标签:Node,559,val,int,ary,Tree,depth,null,children From: https://www.cnblogs.com/Dylan-Java-NYC/p/17107850.html