怎么求出python二叉樹的最大深度

# 怎么求出Python二叉樹的最大深度

## 目錄
1. [二叉樹基礎概念](#二叉樹基礎概念)
2. [最大深度的定義](#最大深度的定義)
3. [遞歸解法](#遞歸解法)
4. [迭代解法（BFS）](#迭代解法bfs)
5. [復雜度分析](#復雜度分析)
6. [完整代碼示例](#完整代碼示例)
7. [應用場景](#應用場景)
8. [總結](#總結)

---

## 二叉樹基礎概念
二叉樹（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或3→20→15）。

遞歸解法

核心思想

• 二叉樹的最大深度 = 1 + max(左子樹深度, 右子樹深度)
• 基線條件：空節點深度為0

代碼實現

def maxDepth(root: TreeNode) -> int:
    if not root:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

執行過程分析

以示例樹為例： 1. 根節點3 → 計算max(左子樹9, 右子樹20) 2. 節點9 → 左右均為空 → 返回1 3. 節點20 → max(左15, 右7) 4. 節點15和7 → 均返回1 5. 最終結果：1 + max(1, 2) = 3

迭代解法（BFS）

廣度優先搜索思路

• 使用隊列按層遍歷
• 每處理完一層，深度+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

執行示例

隊列變化：
[3] → depth=1
[9,20] → depth=2
[15,7] → depth=3
[] → 結束

復雜度分析

• h為樹高度，w為樹最大寬度（最寬層的節點數）

完整代碼示例

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 遞歸解法
def maxDepth_recursive(root: TreeNode) -> int:
    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: 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

# 測試用例
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

應用場景

1. 平衡性檢查：判斷AVL樹是否需要旋轉
2. 文件系統：計算目錄樹的最大嵌套深度
3. 游戲：評估決策樹的最遠可能路徑
4. 網絡路由：確定最優路徑跳數

總結

• 遞歸法代碼簡潔，適合理解樹結構
• BFS法更適合寬而淺的樹結構
• 實際選擇時需考慮：
  • 樹的高度（遞歸棧深度）
  • 是否需要層序遍歷的其他信息

掌握這兩種方法能解決LeetCode 104題及其他衍生問題（如最小深度、直徑等）。 “`

注：實際字符數約1300字（含代碼和格式標記）。如需調整內容細節，可進一步擴展算法原理或增加可視化示例。