首页 > 其他分享 >LeetCode 559. Maximum Depth of N-ary Tree

LeetCode 559. Maximum Depth of N-ary Tree

时间:2023-02-10 09:46:24浏览次数:61  
标签:Node 559 val int ary Tree depth null children

原题链接在这里: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

相关文章