0111. 二叉树的最小深度
小于 1 分钟
0111. 二叉树的最小深度
- 标签:树、深度优先搜索、广度优先搜索
- 难度:简单
题目大意
给定一个二叉树,找出其最小深度。
- 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
解题思路
深度优先搜索递归遍历左右子树,记录最小深度。
对于每一个非叶子节点,计算其左右子树的最小叶子节点深度,将较小的深度+1 即为当前节点的最小叶子节点深度。
代码
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