[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)\),每个节点都需要入栈出栈一次。
方法三: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. 😉😃💗