如何將有序數組轉換為二叉搜索樹

# 如何將有序數組轉換為二叉搜索樹

## 引言

二叉搜索樹（Binary Search Tree, BST）是一種常見的數據結構，它具有以下重要特性：
- 左子樹所有節點值小于根節點值
- 右子樹所有節點值大于根節點值
- 左右子樹也分別是二叉搜索樹

當給定一個**有序數組**時，如何高效地將其轉換為高度平衡的二叉搜索樹？本文將深入探討這個問題，提供多種解決方案，并分析其時間復雜度和空間復雜度。

## 問題定義

給定一個按升序排列的整數數組 `nums`，將其轉換為滿足以下條件的二叉搜索樹：
1. 樹高度平衡（左右子樹高度差不超過1）
2. 保持二叉搜索樹的性質

示例：
```python
輸入: [-10, -3, 0, 5, 9]
輸出:
      0
     / \
   -3   9
   /   /
-10  5

理論基礎

二叉搜索樹的性質

• 中序遍歷BST會得到一個有序數組
• 任意節點的左子樹包含值小于該節點
• 任意節點的右子樹包含值大于該節點

高度平衡的意義

• 保證樹的操作（查找/插入/刪除）時間復雜度為O(log n)
• 避免退化為鏈表（最差情況時間復雜度O(n)）

解決方案

方法一：遞歸分治法（最優解）

算法思路

1. 找到數組中間元素作為根節點
2. 遞歸構建左子樹（左半部分數組）
3. 遞歸構建右子樹（右半部分數組）

Python實現

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

def sortedArrayToBST(nums):
    def helper(left, right):
        if left > right:
            return None
        mid = (left + right) // 2
        root = TreeNode(nums[mid])
        root.left = helper(left, mid - 1)
        root.right = helper(mid + 1, right)
        return root
    
    return helper(0, len(nums) - 1)

復雜度分析

• 時間復雜度：O(n) —— 每個元素訪問一次
• 空間復雜度：O(log n) —— 遞歸棧的深度

方法二：迭代法（使用棧模擬遞歸）

算法思路

1. 使用棧保存待處理的子數組范圍
2. 每次取出范圍，找到中點創建節點
3. 將左右子數組范圍壓入棧

Python實現

def sortedArrayToBST(nums):
    if not nums:
        return None
    
    stack = []
    root = TreeNode()
    stack.append((0, len(nums) - 1, root, 'left'))
    
    while stack:
        left, right, parent, direction = stack.pop()
        mid = (left + right) // 2
        
        if direction == 'left':
            parent.left = TreeNode(nums[mid])
            node = parent.left
        else:
            parent.right = TreeNode(nums[mid])
            node = parent.right
        
        if left <= mid - 1:
            stack.append((left, mid - 1, node, 'left'))
        if mid + 1 <= right:
            stack.append((mid + 1, right, node, 'right'))
    
    return root.left

復雜度分析

• 時間復雜度：O(n)
• 空間復雜度：O(n) —— 最壞情況下棧的深度

方法三：中序遍歷模擬法（進階解法）

算法思路

1. 預先生成空節點樹結構
2. 通過中序遍歷順序填充節點值

Python實現

def sortedArrayToBST(nums):
    def count_nodes(left, right):
        if left > right:
            return 0
        return 1 + count_nodes(left, (left+right)//2 - 1) + count_nodes((left+right)//2 + 1, right)
    
    n = len(nums)
    root = TreeNode()
    stack = [(0, n - 1, root)]
    idx = 0
    
    while stack:
        left, right, node = stack.pop()
        mid = (left + right) // 2
        
        # In-order traversal processing
        if left <= mid - 1:
            node.left = TreeNode()
            stack.append((left, mid - 1, node.left))
        
        node.val = nums[idx]
        idx += 1
        
        if mid + 1 <= right:
            node.right = TreeNode()
            stack.append((mid + 1, right, node.right))
    
    return root

復雜度分析

• 時間復雜度：O(n)
• 空間復雜度：O(n)

算法比較

邊界情況處理

1. 空數組輸入：

   if not nums:
      return None
   

2. 單元素數組：

   if len(nums) == 1:
      return TreeNode(nums[0])
   

3. 大數組處理：

   • 遞歸方法可能棧溢出
   • 建議使用迭代法處理超大數組

實際應用場景

1. 數據庫索引：B樹/B+樹的構建
2. 內存數據庫：高效查詢結構
3. 游戲開發：空間分區樹（如KD樹）
4. 編譯器設計：符號表實現

擴展思考

1. 如何處理有重復元素的數組？

   • 定義左子樹≤根節點或右子樹≥根節點
   • 需要調整平衡策略

2. 如何優化為AVL樹或紅黑樹？

   • 在構建過程中加入旋轉操作
   • 需要額外維護平衡因子

3. 如何支持動態插入/刪除？

   • 需要實現標準的BST插入刪除算法
   • 配合旋轉操作保持平衡

總結

將有序數組轉換為平衡二叉搜索樹是一個經典的算法問題，其核心在于： 1. 利用數組的有序性對應BST的中序遍歷 2. 通過分治法保證樹的平衡性 3. 遞歸是最直觀的解決方案，迭代法則更適合處理大數據量

理解這個問題不僅有助于掌握BST的特性，也是學習分治算法和樹操作的絕佳案例。

參考資料

1. 《算法導論》—— Thomas H. Cormen
2. LeetCode #108 官方題解
3. 《數據結構與算法分析》—— Mark Allen Weiss
4. GeeksforGeeks BST專題

”`