友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
111. Minimum Depth of Binary Tree
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Note: A leaf is a node with no children.
Example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its minimum depth = 2.
思考题
使用深度优先搜索和广度优先搜索来解决这个问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* Runtime: 0 ms, faster than 100.00% of Java online submissions for Minimum Depth of Binary Tree.
* Memory Usage: 40.1 MB, less than 48.44% of Java online submissions for Minimum Depth of Binary Tree.
*/
public int minDepth(TreeNode root) {
if (Objects.isNull(root)) {
return 0;
}
if (Objects.isNull(root.left) && Objects.isNull(root.right)) {
return 1;
}
int min = Integer.MAX_VALUE;
if (Objects.nonNull(root.left)) {
min = Math.min(minDepth(root.left), min);
}
if (Objects.nonNull(root.right)) {
min = Math.min(minDepth(root.right), min);
}
return min + 1;
}
基于 DFS 的解法
代码最简单。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int minDepth(TreeNode root) {
if (Objects.isNull(root)) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
int result = Integer.MAX_VALUE;
if (Objects.nonNull(root.left)) {
result = Math.min(result, minDepth(root.left));
}
if (Objects.nonNull(root.right)) {
result = Math.min(result, minDepth(root.right));
}
return result + 1;
}
基于 Morris 遍历的解法
| 可以换个角度理解这道题：使用 Morris 遍历树时，遍历到每个节点时，计算该节点的深度，然后从中筛选出叶子阶段的深度，取最小值即可。 |
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
* 参考左程云《程序员代码面试指南》的解法
*/
public int minDepth(TreeNode head) {
if (head == null) {
return 0;
}
TreeNode cur = head;
TreeNode mostRight = null;
int curLevel = 0;
int minHeight = Integer.MAX_VALUE;
while (cur != null) {
mostRight = cur.left;
if (mostRight != null) { // 当前 cur 有左子树，能到达两次
// cur 左子树上，右边界的节点个数
int leftTreeRightSize = 1;
// 找到 cur 左子树上最右边的节点
while (mostRight.right != null && mostRight.right != cur) {
leftTreeRightSize++;
mostRight = mostRight.right;
}
if (mostRight.right == null) {
// 第一次到达 cur，那么下一个节点的 level 必然+1
curLevel++;
mostRight.right = cur;
cur = cur.left;
continue;
} else {
// 第二次到达cur，那么下一个节点的 level = curLevel - leftTreeRightSize
// 此时检查 mostRight 是不是叶节点，记录答案
if (mostRight.left == null) {
minHeight = Math.min(minHeight, curLevel);
}
curLevel -= leftTreeRightSize;
mostRight.right = null;
}
} else {
// 当前 cur 没有左子树，只能到达有ICI，那么下一个节点的 level 必然+1
curLevel++;
}
cur = cur.right;
}
int finalRight = 1;
cur = head;
while (cur.right != null) {
finalRight++;
cur = cur.right;
}
// 最后不要忘了单独看一看整棵树的最右节点是不是叶节点
if (cur.left == null && cur.right == null) {
minHeight = Math.min(minHeight, finalRight);
}
return minHeight;
}
竟然在 LeetCode 中文站点没有找到使用 Morris 遍历方法处理的解答。
基于 BFS 的解法
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
/**
* 参考左程云《程序员代码面试指南》的解法
*/
public int minDepth(TreeNode head) {
if (head == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(head);
int depth = 0;
while (!queue.isEmpty()) {
int size = queue.size();
depth++;
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left == null && node.right == null) {
return depth;
} else {
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
}
return depth;
}