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

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 2.1k 阅读时长 ≈ 2 分钟

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. 😉😃💗