【Leetcode Daily】114二叉树的最小深度

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是规定二叉树的深度是从根节点到叶子节点的节点数，求二叉树的最小深度。

思路分享

• 和 【Leetcode Daily】104二叉树的最大深度 十分相关，关于自顶向下和自底向上的区别说明等不在此赘述。

  https://leetcode.cn/problems/minimum-depth-of-binary-tree/solutions/2730984/liang-chong-fang-fa-zi-ding-xiang-xia-zi-0sxz/

代码解答（强烈建议自行解答后再看）

• 参考题解

# 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
        if not root.left and not root.right:
            return 1
        if not root.left:
            return self.minDepth(root.right) +1
        if not root.right:
            return self.minDepth(root.left) + 1
        return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
        
        # 自顶向下
        if not root:
            return 0
        ans = inf
        def dfs(root: Optional[TreeNode], depth:int) -> int:
            if not root:
                return
            if not root.left and not root.right:
                nonlocal ans
                ans = min(ans, depth+1)
                return 
            dfs(root.left, depth+1)
            dfs(root.right, depth+1)
        dfs(root, 0)
        return ans