目錄
題目解釋
給定 binary tree 的 root
,返回其最大深度。
Binary tree 的最大深度是從 root
到最遠 leaf node 的最長路徑上的 node 數。
範例
- 輸入:
root = [3, 9, 20, null, null, 15, 7]
- 輸出:
3
root
到最遠且同層的 15
或 7
的節點數量都是 3
。
最佳解法
在寫 Tree 的題目時,最重要的就是 遞迴 (Recursion) 的概念。
我們可以把這題拆解為
- 遞迴的處理左子樹
- 遞迴的處理右子樹
- 回傳左右深度的最大值 + 1 (一定是多走了一層才會走到這)
說明
因為如果透過一個變數去記遞迴中的 depth 的話,不僅繁瑣還容易出錯,
我們索性將 return 的數值做為當前遞迴的最大 depth。
我們會不斷的先往左邊走,都 return 回根節點後再來才是向右走,
所以這是一種 深度優先探索 (DFS) 的演算法。
程式碼
拆的比較細的遞迴版
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
def _dfs(root):
if not root:
return 0
else:
left_max_depth = _dfs(root.left)
right_max_depth = _dfs(root.right)
return max(left_max_depth, right_max_depth) + 1
return _dfs(root)
蝦趴簡約遞迴版
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
用 stack 的 DFS 實作
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
stack = [[root, 0]]
max_depth = 0
while stack:
node, depth = stack.pop()
max_depth = max(max_depth, depth)
if node:
stack.append([node.left, depth + 1])
stack.append([node.right, depth + 1])
return max_depth
用 queue 的 BFS 實作
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
queue = deque([root])
level = 0
while queue:
for i in range(len(queue)):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
level += 1
return level
時間複雜度
O(n)
,n 是 binary tree 的 node 個數。
空間複雜度
O(h)
,h 是 binary tree 的高度。
結語
Tree 的 pattern 要熟記 (繼續對自己喊話)
Latest posts by 數據女巫 𝔻.𝕡𝕪𝕤 🔮 (see all)
- [推薦工具] 讓程式碼截圖變的美美的吧!VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
- [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
- [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26