二叉樹的最小深度
題目：給定一個二叉樹洽议，找出其最小深度。
最小深度是從根節(jié)點到最近葉子節(jié)點的最短路徑上的節(jié)點數量。
說明: 葉子節(jié)點是指沒有子節(jié)點的節(jié)點硼端。
思路：與求二叉樹的高度思路相似，不過要注意遞歸條件如下寓搬。
- 當節(jié)點為空珍昨，return 0
- 當節(jié)點左節(jié)點為空，return 節(jié)點右子樹的最小深度句喷。
- 當節(jié)點右節(jié)點為空镣典，return 節(jié)點左子樹最小深度。
- 當節(jié)點左右節(jié)點都不為空時唾琼，rerturn 左右子樹最小深度骆撇。
說明：注意當節(jié)點有一個節(jié)點為空而另一個節(jié)點不為空，如2父叙，3條時神郊，不應該返回左右子樹的最小深度，因為最小深度的定義是從根節(jié)點到最近葉子節(jié)點的最短路徑上的節(jié)點數量趾唱，如果在2涌乳，3這兩種情況返回左右子樹的最小深度就會導致得到的是非葉子節(jié)點的最小深度不滿足題意。
代碼如下：
class Solution:
def minDepth(self, root: TreeNode) -> int:
if root is None or root.val is None:
return 0
if root.left is None and root.right is None:
return 1
if root.left is None:
return self.minDepth(root.right) + 1
if root.right is None:
return self.minDepth(root.left) + 1
return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
