111.二叉樹的最小深度

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

root1 = TreeNode(1)
root2 = TreeNode(2)
root1.left = root2
# 這道題也是遞歸的想法，遍歷每個子樹，跟上一題的方法一樣
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        return self.dfs(root)
    def dfs(self,root):
        # 首先判斷根節點是否為None
        if not root : return 0
        # 分別求出左子樹和右子樹的最小路徑
        left = self.dfs(root.left)
        right = self.dfs(root.right)
        # 註意這裡一定要加判斷的原因
        # 是因為，當左節點或者右節點為空的時候不能算在路徑裡邊
        if left == 0 and right != 0:
            return right + 1
        elif left != 0 and right == 0:
            return left + 1
        # 返回左子樹和右子樹中最小的路徑，當然，還要加上根節點。
        return min(left,right) + 1
a = Solution()
print(a.minDepth(root1))