給定一個二叉樹，找出其最小深度。

最小深度是從根節點到最近葉子節點的最短路徑上的節點數量。

說明:?葉子節點是指沒有子節點的節點。

示例:

給定二叉樹?[3,9,20,null,null,15,7],

3/ \9 20/ \15 7

返回它的最小深度 ?2.

DFS

首先可以想到使用深度優先搜索的方法，遍歷整棵樹，記錄最小深度。

對于每一個非葉子節點，我們只需要分別計算其左右子樹的最小葉子節點深度。這樣就將一個大問題轉化為了小問題，可以遞歸地解決該問題。

Code

def minDepth(self, root: TreeNode) -> int:if not root:return 0if not root.left and not root.right:return 1minDepth = 10 ** 9if root.left:minDepth = min(self.minDepth(root.left), minDepth)if root.right:minDepth = min(self.minDepth(root.right), minDepth)return minDepth + 1

復雜度分析

• 時間復雜度：$O(N)$，其中 $N$ 是樹的節點數。對每個節點訪問一次。

• 空間復雜度：$O(H)$，其中 $H$ 是樹的高度。空間復雜度主要取決于遞歸時棧空間的開銷，最壞情況下，樹呈現鏈狀，空間復雜度為 $O(N)$。平均情況下樹的高度與節點數的對數正相關，空間復雜度為 $O(\log N)$。

總結

以上是生活随笔為你收集整理的111. Minimum Depth of Binary Tree 二叉树的最小深度的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。