-
Notifications
You must be signed in to change notification settings - Fork 4
/
MaximumDepthOfNaryTree.java
104 lines (97 loc) · 2.43 KB
/
MaximumDepthOfNaryTree.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
package algorithms;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/**
* 559. Maximum Depth of N-ary Tree
* https://leetcode.com/problems/maximum-depth-of-n-ary-tree/
* Difficulty : Easy
* Related Topics : Depth-first Search, Breadth-first Search
*
* 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:
* https://assets.leetcode.com/uploads/2018/10/12/narytreeexample.png
*
* Input: root = [1,null,3,2,4,null,5,6]
* Output: 3
*
* Example 2:
* https://assets.leetcode.com/uploads/2019/11/08/sample_4_964.png
*
* 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 depth of the n-ary tree is less than or equal to 1000.
* The total number of nodes is between [0, 10^4].
*
*
* // Definition for a Node.
* class Node {
* public int val;
* public List<Node> children;
*
* public Node() {}
*
* public Node(int _val) {
* val = _val;
* }
*
* public Node(int _val, List<Node> _children) {
* val = _val;
* children = _children;
* }
* };
*
* created by cenkc on 8/12/2020
*/
public class MaximumDepthOfNaryTree {
/**
* Runtime: 1 ms
* Memory Usage: 40.2 MB
*
* @param root
* @return
*/
public int maxDepth(Node root) {
if (root == null) {
return 0;
}
Queue<Node> q = new LinkedList<>();
q.offer(root);
int level = 0;
while ( ! q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
Node currNode = q.poll();
List<Node> children = currNode.children;
for (Node child : children) {
q.offer(child);
}
}
level++;
}
return level;
}
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
}
}