111. 二叉树的最小深度

• 题目
• 完美踩坑
• 题解

题目

• 给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：2

示例 2：

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

完美踩坑

• 之前好几个题做过求树的高度，以为只需要把返回左右子树较大的一个改为返回左右子树较小的一个就可以了。

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        # 求树的高度
        if root is None:
            return 0
        return min(self.minDepth(root.left),self.minDepth(root.right))+1

• 当遇到左/右子树空时，上面代码会返回1，把根节点认为是叶子节点，实际上返回的不是1而是不为空的子树那边的叶子节点到根节点的距离。

题解

• 单独处理左/右子树为空的情况

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        # 空树
        if root is None:
            return 0
        #只有根节点
        if root.left is None and root.right is None:
            return 1
        #当只有左子树
        if root.left is None and root.right is not None:
            return self.minDepth(root.right)+1
        #当只有右子树
        if root.left is not None and root.right is None:
            return self.minDepth(root.left)+1
        #左右子树都有
        return min(self.minDepth(root.left),self.minDepth(root.right))+1