[Leetcode][559. N叉树的最大深度] 3种方法:递归,DFS和BFS

By Long Luo

Leetcode 559. N叉树的最大深度 题解。

方法一:递归

思路与算法:

类似树的深度问题,都可以使用递归实现:

  1. 确定递归的参数和返回值:参数就是传入树的根节点,返回值就是树的深度;
  2. 确定终止条件:如果为空节点的话,就返回0,表示高度为0;
  3. 确定单层递归的逻辑:如果是二叉树,那么先求它的左子树的深度,再求的右子树的深度,最后取左右深度最大的数值,最后再+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)\),每个节点都需要入栈出栈一次。

方法三:BFS

思路与算法:

使用BFS进行求解,实质是对多叉树进行分层处理BFS队列里存放的是当前层的所有节点。

值得注意的是,因为队列Queue会不断增加,所以必须从size往下添加。

每次拓展下一层的时候,需要将队列里的所有节点都拿出来进行拓展,当过程结束,意味着达到最大层数,所记录的最大层数即是答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// BFS time: O(n) space: O(n)
public int maxDepth_bfs_opt(Node root) {
if (root == null) {
return 0;
}

int ans = 0;
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
ans++;
int size = queue.size();
while (size > 0) {
Node node = queue.poll();
for (Node child : node.children) {
queue.offer(child);
}
size--;
}
}

return ans;
}

复杂度分析:

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

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


All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗