题目
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明:叶子节点是指没有子节点的节点。
示例 1:
输入:root = [3,9,20,null,null,15,7]
输出:2
示例 2:
输入:root = [2,null,3,null,4,null,5,null,6]
输出:5
提示:
树中节点数的范围在 [0, 105] 内
-1000 <= Node.val <= 1000
思路
这题被阴了一把,看着和最大深度一样,实则不同。比如单分支的情况,直接照着最大深度把max改成min返回的结果是1,但实际上应该返回单分支的节点个数。
测一下这个样例就知道了:
输入:root = [2,null,3,null,4,null,5,null,6] 输出:5
所以这里需要加入一些限定条件,把单分支的情况考虑进去,可以参考代码,也不难。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
left = self.minDepth(root.left)
right = self.minDepth(root.right)
if left==0 and right==0:
return 1
elif left==0:
return right + 1
elif right==0:
return left + 1
return min(left,right) + 1