题目大意
#
给定一个二叉树,找出其最小深度。
- 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
解题思路
#
深度优先搜索递归遍历左右子树,记录最小深度。
对于每一个非叶子节点,计算其左右子树的最小叶子节点深度,将较小的深度+1 即为当前节点的最小叶子节点深度。
代码
#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution:
def minDepth(self, root: TreeNode) -> int:
# 遍历到空节点,直接返回 0
if root == None:
return 0
# 左右子树为空,说明为叶子节点 返回 1
if root.left == None and root.right == None:
return 1
leftHeight = self.minDepth(root.left)
rightHeight = self.minDepth(root.right)
# 当前节点的左右子树的最小叶子节点深度
min_depth = 0xffffff
if root.left:
min_depth = min(leftHeight, min_depth)
if root.right:
min_depth = min(rightHeight, min_depth)
# 当前节点的最小叶子节点深度
return min_depth + 1
|