題目:

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

給定一個binary tree,求root到leaf的最短路徑

這題有點104.變體感

# 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 root.left and root.right:
            return min(self.minDepth(root.left),self.minDepth(root.right))+1
        else:
            if root.left:
                return self.minDepth(root.left)+1
            elif root.right:
                return self.minDepth(root.right)+1
            else:
                return 1

不過這次遇到leaf就要回傳1(leaf自己也算一層)往上加了
因為我們這次是左右子樹比小
假如一側是None回傳0會導致判斷失誤(因為那裡其實沒節點,但取min會取到0)
最後得到的值就是root到leaf的最短路徑了
最後執行時間537ms(faster than 94.44%)

那我們下題見