[Leetcode][559. N叉树的最大深度] 3种方法：递归，DFS和BFS
By Long Luo
方法一：递归
思路与算法：
类似树的深度问题，都可以使用递归实现：
- 确定递归的参数和返回值：参数就是传入树的根节点，返回值就是树的深度；
- 确定终止条件：如果为空节点的话，就返回0，表示高度为0；
- 确定单层递归的逻辑：如果是二叉树，那么先求它的左子树的深度，再求的右子树的深度，最后取左右深度最大的数值，最后再+1（加1是因为算上当前中间节点）就是目前节点为根节点的树的深度。
具体到N叉树，代码如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13// Recursion time: O(n) space: O(n)
public int maxDepth(Node root) {
if (root == null) {
return 0;
}
int ans = 0;
for (Node child : root.children) {
ans = Math.max(ans, maxDepth(child));
}
return ans + 1;
}
复杂度分析
- 时间复杂度：\(O(n)\)，其中\(n\)为\(N\)叉树节点的个数。每个节点在递归中只被遍历一次。
- 空间复杂度：\(O(\textit{height})\)，其中\(\textit{height}\)表示\(N\)叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于\(N\)叉树的高度。
方法二：DFS迭代
二叉树的遍历，其实也是DFS的一种方式，我们可以参考二叉树的遍历，使用迭代的方式进行遍历，最后更新\(N\)叉树的最大深度。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// DFS time: O(n) space: O(n)
class Pair {
Node node;
int depth;
Pair(Node node, int depth) {
this.node = node;
this.depth = depth;
}
}
public int maxDepth_dfs(Node root) {
if (root == null) {
return 0;
}
int ans = 0;
Stack<Pair> stack = new Stack<>();
stack.push(new Pair(root, 1));
while (!stack.empty()) {
Pair top = stack.pop();
Node node = top.node;
int depth = top.depth;
for (Node childNode : node.children) {
stack.push(new Pair(childNode, depth + 1));
}
ans = Math.max(ans, depth);
}
return ans;
}
复杂度分析
- 时间复杂度：\(O(n)\)，其中\(n\)为\(N\)叉树节点的个数。
- 空间复杂度：\(O(n)\)，每个节点都需要入栈出栈一次。