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.
My Solution
We can solve this problem with depth first search. If the root is null, we return 0. If it is a leaf node, we return 1. Otherwise, recursively return the maximum depth among each of its children.
Time complexity is O(n), because we traverse every node. Space complexity is O(log n) due to the space required on the call stack.
/*
// 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;
}
};
*/
class Solution {
public int maxDepth(Node root) {
if (root == null) {
return 0;
}
if (root.children.size() == 0) {
return 1;
}
int max = 0;
for (int i = 0; i < root.children.size(); i++) {
Node child = root.children.get(i);
max = Math.max(max, 1 + maxDepth(child));
}
return max;
}
}