【Leetcode算法题】559. N叉树的最大深度

By Long Luo

今天Leetcode的每日一题是:559. N叉树的最大深度,题目如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
559. N叉树的最大深度

给定一个 N 叉树,找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
N叉树输入按层序遍历序列化表示,每组子节点由空值分隔(请参见示例)。

示例 1:
输入:root = [1,null,3,2,4,null,5,6]
输出:3

示例 2:
输入: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]
输出:5

提示:
树的深度不会超过 1000 。
树的节点数目位于 [0, 104] 之间。

方法一:DFS

思路与算法:

代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int maxDepth(Node root) {
if (root == null) {
return 0;
} else if (root.children.isEmpty()) {
return 1;
} else {
List<Integer> depthList = new LinkedList<>();
for (Node child : root.children) {
depthList.add(maxDepth(child));
}

return Collections.max(depthList) + 1;
}
}

复杂度分析:

  • 时间复杂度:O(n)O(n),其中nnNN叉树节点的个数。每个节点在递归中只被遍历一次。

  • 空间复杂度:O(height)O(\textit{height}),其中height\textit{height}表示NN叉树的高度。递归函数需要栈空间,而栈空间取决于递归的深度,因此空间复杂度等价于NN叉树的高度。

方法二:BFS

思路与算法:

比较简单,代码如下所示:

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
static class QueueNode {
Node node;
int depth;

QueueNode(Node node, int depth) {
this.node = node;
this.depth = depth;
}
}

public static int maxDepth(Node root) {
if (root == null) {
return 0;
}

Queue<QueueNode> queue = new LinkedList<>();
queue.offer(new QueueNode(root, 1));
int maxDepth = 0;
while (!queue.isEmpty()) {
QueueNode queueNode = queue.poll();
Node node = queueNode.node;
int depth = queueNode.depth;
maxDepth = Math.max(depth, maxDepth);
if (node.children != null) {
List<Node> children = node.children;
for (Node child : children) {
if (child != null) {
queue.offer(new QueueNode(child, depth + 1));
}
}
}
}

return maxDepth;
}

复杂度分析:

  • 时间复杂度:O(n)O(n),其中nnNN叉树的节点个数。与方法一同样的分析,每个节点只会被访问一次。

  • 空间复杂度:此方法空间的消耗取决于队列存储的元素数量,其在最坏情况下会达到O(n)O(n)