长大后想做什么?做回小孩!

0%

LeetCode——二叉树的最小深度

NO.111 二叉树的最小深度 简单

JE4zcQ.png

思路一:深搜 又是求树深度的问题,求最小深度,左右子树都为空的节点是叶子节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
public int minDepth(TreeNode root) {
if (root == null) return 0;
//左右子树的深度
int left = minDepth(root.left);
int right = minDepth(root.right);
//左右子树都为空,找到叶子节点,返回根节点1
//如果有一边为空,则返回非空一侧的深度+根节点
if (left == 0 || right == 0) {
return left + right + 1;
}
//最后计算深度最小的一侧+根节点
return Math.min(left, right) + 1;
}

时间复杂度:O(n) 深度优先遍历一次


本人菜鸟,有错误请告知,感激不尽!

更多题解和源码:github