Poison

559. Maximum Depth of N-ary Tree

发表于
DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxDepth(Node root) {
        if (root == null) {
            return 0;
        }

        int maxDepth = 0;
        if (root.children != null) {
            for (Node childNode : root.children) {
                maxDepth = Math.max(maxDepth(childNode), maxDepth);
            }
        }

        return maxDepth + 1;
    }
}
BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int maxDepth(Node root) {
        int depth = 0;
        Queue<Node> queue = new LinkedList<>();
        if (root != null) {
            queue.add(root);
        }

        while (!queue.isEmpty()) {
            for (int i = queue.size(); i > 0; i--) {
                Node node = queue.poll();
                if (node.children != null && !node.children.isEmpty()) {
                    queue.addAll(node.children);
                }
            }

            depth++;
        }

        return depth;
    }
}
Reference

559. Maximum Depth of N-ary Tree