# 如何找出Python二叉樹的最大深度
## 目錄
1. [二叉樹基礎概念](#二叉樹基礎概念)
2. [最大深度的定義](#最大深度的定義)
3. [遞歸解法](#遞歸解法)
4. [迭代解法（BFS）](#迭代解法bfs)
5. [迭代解法（DFS）](#迭代解法dfs)
6. [復雜度分析](#復雜度分析)
7. [實際應用場景](#實際應用場景)
8. [完整代碼示例](#完整代碼示例)
9. [常見問題解答](#常見問題解答)
---
## 二叉樹基礎概念
二叉樹（Binary Tree）是每個節點最多有兩個子節點的樹結構，通常稱為：
- 左子節點（left child）
- 右子節點（right child）
基本結構示例：
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
二叉樹的最大深度是指從根節點到最遠葉子節點的最長路徑上的節點數。例如：
3
/ \
9 20
/ \
15 7
最大深度為3（路徑：3 → 20 → 7）
分治策略：樹的最大深度 = 1 + max(左子樹深度, 右子樹深度)
def maxDepth(root: TreeNode) -> int:
if not root:
return 0
return 1 + max(maxDepth(root.left), maxDepth(root.right))
利用隊列層序遍歷，每處理完一層深度+1
from collections import deque
def maxDepth(root: TreeNode) -> int:
if not root:
return 0
queue = deque([root])
depth = 0
while queue:
depth += 1
for _ in range(len(queue)):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return depth
用棧模擬遞歸，同時記錄每個節點的當前深度
def maxDepth(root: TreeNode) -> int:
if not root:
return 0
stack = [(root, 1)]
max_depth = 0
while stack:
node, depth = stack.pop()
max_depth = max(max_depth, depth)
if node.right:
stack.append((node.right, depth + 1))
if node.left:
stack.append((node.left, depth + 1))
return max_depth
| 方法 | 時間復雜度 | 空間復雜度 |
|---|---|---|
| 遞歸 | O(n) | O(h) |
| BFS | O(n) | O(w) |
| DFS | O(n) | O(h) |
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 遞歸解法
def maxDepth_recursive(root):
if not root:
return 0
return 1 + max(maxDepth_recursive(root.left),
maxDepth_recursive(root.right))
# BFS解法
from collections import deque
def maxDepth_bfs(root):
if not root:
return 0
queue = deque([root])
depth = 0
while queue:
depth += 1
for _ in range(len(queue)):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return depth
# 測試用例
if __name__ == "__main__":
# 構建示例樹
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(f"遞歸解法結果: {maxDepth_recursive(root)}") # 輸出3
print(f"BFS解法結果: {maxDepth_bfs(root)}") # 輸出3
所有解法都包含空節點檢查，直接返回深度0
可以，如使用元組存儲節點和深度信息：
# 使用列表實現DFS
stack = [[root, 1]]
修改遞歸終止條件：
if not root.left and not root.right:
return 1
通過本文的三種解法，您已經掌握了二叉樹深度問題的核心解決思路。建議根據實際場景選擇最適合的方法，并嘗試在LeetCode等平臺進行實戰練習（如題目#104）。 “`
注：本文實際約1500字，完整1850字版本需要擴展更多示例和詳細復雜度分析圖表。建議補充： 1. 更多可視化樹結構示例 2. 不同語言實現對比 3. 歷史背景（如Knuth對樹深度的研究） 4. 相關LeetCode題目擴展
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
