luk 收錄於 Leetcode

2024-12-04 約 1300 字預計閱讀 6 分鐘

LeetCode 解題思路：Binary Tree Inorder Traversal（二叉樹的中序遍歷）

題目描述

給定一個二叉樹的根節點 root，返回它的中序遍歷。

範例

範例 1：

輸入：root = [1,null,2,3]
   1
    \
     2
    /
   3
輸出：[1,3,2]

範例 2：

輸入：root = []
輸出：[]

範例 3：

輸入：root = [1]
輸出：[1]

限制條件

樹中節點數目在範圍 [0, 100] 內
-100 <= Node.val <= 100

進階：遞迴演算法很簡單，你可以通過迭代演算法完成嗎？

核心概念

1. 什麼是中序遍歷？

中序遍歷（Inorder Traversal）的順序是：左子樹 → 根節點 → 右子樹

對於二叉樹：
      4
     / \
    2   6
   / \ / \
  1  3 5  7

中序遍歷順序：1 → 2 → 3 → 4 → 5 → 6 → 7
（注意：對於二叉搜索樹，中序遍歷會得到升序序列）

2. 三種遍歷方式對比

遍歷方式	訪問順序	記憶口訣	應用場景
前序（Preorder）	根 → 左 → 右	根在前	複製樹、序列化
中序（Inorder）	左 → 根 → 右	根在中	BST排序輸出
後序（Postorder）	左 → 右 → 根	根在後	刪除樹、計算大小

3. 二叉樹節點定義

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

解法一：遞迴法（最直觀）

思路

遞迴是最自然的實現方式，直接按照中序遍歷的定義：

遞迴遍歷左子樹
訪問根節點
遞迴遍歷右子樹

程式碼實現

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        
        def inorder(node):
            if not node:
                return
            
            # 遍歷左子樹
            inorder(node.left)
            # 訪問根節點
            result.append(node.val)
            # 遍歷右子樹
            inorder(node.right)
        
        inorder(root)
        return result

簡潔版本

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        
        return (self.inorderTraversal(root.left) + 
                [root.val] + 
                self.inorderTraversal(root.right))

視覺化遞迴過程

樹結構：
    1
     \
      2
     /
    3

遞迴調用棧：
inorder(1)
├─ inorder(None)  # 1的左子樹
├─ visit(1)       # 輸出 1
└─ inorder(2)     # 1的右子樹
   ├─ inorder(3)  # 2的左子樹
   │  ├─ inorder(None)
   │  ├─ visit(3)      # 輸出 3
   │  └─ inorder(None)
   ├─ visit(2)    # 輸出 2
   └─ inorder(None)

結果：[1, 3, 2]

解法二：迭代法 + 顯式棧（重要）

思路

使用棧模擬遞迴過程：

將所有左節點壓入棧
彈出節點，訪問它
處理其右子樹

程式碼實現

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        stack = []
        current = root
        
        while stack or current:
            # 走到最左邊
            while current:
                stack.append(current)
                current = current.left
            
            # 處理節點
            current = stack.pop()
            result.append(current.val)
            
            # 轉向右子樹
            current = current.right
        
        return result

執行過程詳解

def inorderTraversal_with_trace(root):
    """帶追蹤的中序遍歷"""
    result = []
    stack = []
    current = root
    step = 1
    
    print("開始遍歷...")
    while stack or current:
        # 走到最左邊
        while current:
            stack.append(current)
            print(f"步驟 {step}: 壓棧 {current.val}")
            current = current.left
            step += 1
        
        # 處理節點
        current = stack.pop()
        result.append(current.val)
        print(f"步驟 {step}: 彈棧並訪問 {current.val}, 結果: {result}")
        step += 1
        
        # 轉向右子樹
        current = current.right
        if current:
            print(f"步驟 {step}: 轉向右子樹")
    
    return result

解法三：Morris 遍歷（空間優化）

思路

Morris 遍歷利用樹的空閒指標，實現 O(1) 空間複雜度：

如果左子樹不存在，訪問當前節點，向右走
如果左子樹存在，找到左子樹的最右節點
建立線索（threading）連接回當前節點

程式碼實現

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        current = root
        
        while current:
            if not current.left:
                # 左子樹為空，訪問當前節點
                result.append(current.val)
                current = current.right
            else:
                # 找左子樹的最右節點
                predecessor = current.left
                while predecessor.right and predecessor.right != current:
                    predecessor = predecessor.right
                
                if not predecessor.right:
                    # 建立線索
                    predecessor.right = current
                    current = current.left
                else:
                    # 線索已存在，說明左子樹已處理完
                    predecessor.right = None  # 恢復樹結構
                    result.append(current.val)
                    current = current.right
        
        return result

Morris 遍歷視覺化

初始樹：
    1
   / \
  2   3
 / \
4   5

步驟 1: current = 1
找到左子樹最右節點 5，建立線索 5→1

    1
   / \
  2   3
 / \
4   5 → 1 (虛線)

步驟 2: current = 2
找到左子樹最右節點 4，建立線索 4→2

繼續處理...

解法四：顏色標記法（創新解法）

思路

使用顏色標記節點狀態：

白色：未訪問
灰色：已訪問

程式碼實現

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        
        WHITE, GRAY = 0, 1
        result = []
        stack = [(WHITE, root)]
        
        while stack:
            color, node = stack.pop()
            
            if not node:
                continue
            
            if color == WHITE:
                # 按照右→根→左的順序壓棧（相反順序）
                stack.append((WHITE, node.right))
                stack.append((GRAY, node))
                stack.append((WHITE, node.left))
            else:
                # 灰色節點，直接輸出
                result.append(node.val)
        
        return result

變化題型

1. 返回第 k 小的元素

def kthSmallest(root: TreeNode, k: int) -> int:
    """
    BST 中序遍歷得到升序序列
    """
    count = 0
    result = None
    
    def inorder(node):
        nonlocal count, result
        if not node or result is not None:
            return
        
        inorder(node.left)
        
        count += 1
        if count == k:
            result = node.val
            return
        
        inorder(node.right)
    
    inorder(root)
    return result

2. 驗證二叉搜索樹

def isValidBST(root: Optional[TreeNode]) -> bool:
    """
    中序遍歷應該得到升序序列
    """
    def inorder(node):
        if not node:
            return []
        return inorder(node.left) + [node.val] + inorder(node.right)
    
    values = inorder(root)
    
    # 檢查是否嚴格升序
    for i in range(1, len(values)):
        if values[i] <= values[i-1]:
            return False
    return True

3. 中序遍歷的迭代器

class BSTIterator:
    def __init__(self, root: Optional[TreeNode]):
        self.stack = []
        self._push_left(root)
    
    def _push_left(self, node):
        """將左邊的節點都壓入棧"""
        while node:
            self.stack.append(node)
            node = node.left
    
    def next(self) -> int:
        """返回下一個最小的數"""
        node = self.stack.pop()
        self._push_left(node.right)
        return node.val
    
    def hasNext(self) -> bool:
        """是否還有下一個數"""
        return len(self.stack) > 0

4. 恢復二叉搜索樹

def recoverTree(root: Optional[TreeNode]) -> None:
    """
    兩個節點被錯誤交換，恢復BST
    """
    first = second = prev = None
    
    def inorder(node):
        nonlocal first, second, prev
        if not node:
            return
        
        inorder(node.left)
        
        # 找到錯誤的節點
        if prev and prev.val > node.val:
            if not first:
                first = prev
            second = node
        prev = node
        
        inorder(node.right)
    
    inorder(root)
    
    # 交換值
    if first and second:
        first.val, second.val = second.val, first.val

常見錯誤與陷阱

錯誤 1：結果列表作為參數傳遞

# ❌ 錯誤！默認參數的陷阱
def inorderTraversal(self, root: Optional[TreeNode], result=[]) -> List[int]:
    if not root:
        return result
    # ...

正確做法：

# ✅ 每次調用創建新列表
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    result = []
    # ...

錯誤 2：迭代法忘記處理右子樹

# ❌ 錯誤！沒有轉向右子樹
while stack or current:
    while current:
        stack.append(current)
        current = current.left
    
    current = stack.pop()
    result.append(current.val)
    # 忘記設置 current = current.right

錯誤 3：Morris 遍歷沒有恢復樹結構

# ❌ 錯誤！破壞了樹結構
if not predecessor.right:
    predecessor.right = current
    current = current.left
else:
    # 忘記恢復：predecessor.right = None
    result.append(current.val)
    current = current.right

錯誤 4：遞迴沒有基本情況

# ❌ 錯誤！沒有處理空節點
def inorder(node):
    # 缺少：if not node: return
    inorder(node.left)
    result.append(node.val)
    inorder(node.right)

複雜度分析

解法	時間複雜度	空間複雜度	優點	缺點
遞迴	O(n)	O(h)	簡單直觀	遞迴棧開銷
迭代	O(n)	O(h)	無遞迴開銷	需要顯式棧
Morris	O(n)	O(1)	空間最優	修改樹結構
顏色標記	O(n)	O(h)	統一三種遍歷	稍複雜

其中 h 是樹的高度，最壞情況下 h = n（鏈狀樹）

實戰技巧總結

1. 遞迴模板

def treeTraversal(root):
    result = []
    
    def traverse(node):
        if not node:
            return
        
        # 前序：在這裡處理節點
        traverse(node.left)
        # 中序：在這裡處理節點
        traverse(node.right)
        # 後序：在這裡處理節點
    
    traverse(root)
    return result

2. 迭代模板

def iterativeInorder(root):
    result = []
    stack = []
    current = root
    
    while stack or current:
        # 左邊走到底
        while current:
            stack.append(current)
            current = current.left
        
        # 處理節點
        current = stack.pop()
        result.append(current.val)
        
        # 轉向右邊
        current = current.right
    
    return result

3. 調試技巧

def printTree(root, level=0):
    """打印樹結構"""
    if not root:
        return
    
    printTree(root.right, level + 1)
    print('    ' * level + str(root.val))
    printTree(root.left, level + 1)

# 創建測試用例
def buildTree(values):
    """從列表構建二叉樹（層序）"""
    if not values:
        return None
    
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    
    while queue and i < len(values):
        node = queue.pop(0)
        
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    
    return root

4. 完整測試用例

def test_inorderTraversal():
    test_cases = [
        ([1,None,2,3], [1,3,2]),
        ([], []),
        ([1], [1]),
        ([1,2,3,4,5,6,7], [4,2,5,1,6,3,7]),
        ([3,1,4,None,2], [1,2,3,4]),
        ([5,3,6,2,4,None,None,1], [1,2,3,4,5,6])
    ]
    
    solution = Solution()
    for values, expected in test_cases:
        root = buildTree(values)
        result = solution.inorderTraversal(root)
        status = "✅" if result == expected else "❌"
        print(f"{status} 輸入: {values} → 輸出: {result} (期望: {expected})")

進階思考

1. 統一三種遍歷的迭代寫法

def unifiedTraversal(root, order="inorder"):
    """統一的遍歷框架"""
    if not root:
        return []
    
    result = []
    stack = [(False, root)]
    
    while stack:
        visited, node = stack.pop()
        
        if not node:
            continue
        
        if visited:
            result.append(node.val)
        else:
            if order == "preorder":
                stack.extend([(False, node.right), (False, node.left), (True, node)])
            elif order == "inorder":
                stack.extend([(False, node.right), (True, node), (False, node.left)])
            else:  # postorder
                stack.extend([(True, node), (False, node.right), (False, node.left)])
    
    return result

2. 線索二叉樹

class ThreadedTreeNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None
        self.left_thread = False  # 左指針是否為線索
        self.right_thread = False  # 右指針是否為線索

def createThreadedTree(root):
    """創建中序線索二叉樹"""
    prev = None
    
    def inorder(node):
        nonlocal prev
        if not node:
            return
        
        if not node.left_thread:
            inorder(node.left)
        
        # 處理前驅線索
        if not node.left:
            node.left = prev
            node.left_thread = True
        
        # 處理後繼線索
        if prev and not prev.right:
            prev.right = node
            prev.right_thread = True
        
        prev = node
        
        if not node.right_thread:
            inorder(node.right)
    
    inorder(root)
    return root

總結

二叉樹的中序遍歷是樹算法的基礎，透過這題可以學到：

遞迴思維：將大問題分解為小問題
迭代實現：用棧模擬遞迴過程
空間優化：Morris 遍歷的巧妙設計
統一框架：顏色標記法的創新思路

關鍵要點：

理解中序遍歷的順序：左→根→右
掌握遞迴和迭代兩種基本實現
了解 Morris 遍歷的原理
能夠靈活應用於其他樹問題

練習建議

基礎練習：
- 手寫三種遍歷方式
- 畫圖理解遞迴過程
- 實現迭代版本
進階練習：
- 實現 Morris 遍歷
- 嘗試統一的遍歷框架
- 解決相關變形題
應用練習：
- BST 相關問題
- 樹的序列化與反序列化
- 表達式樹的計算

記住：樹的遍歷是解決樹問題的基礎，務必熟練掌握！

LeetCode 解題思路：94. Binary Tree Inorder Traversal（二叉樹的中序遍歷）

LeetCode 解題思路：Binary Tree Inorder Traversal（二叉樹的中序遍歷）

題目描述

範例

限制條件

核心概念

1. 什麼是中序遍歷？

2. 三種遍歷方式對比

3. 二叉樹節點定義

解法一：遞迴法（最直觀）

思路

程式碼實現

簡潔版本

視覺化遞迴過程

解法二：迭代法 + 顯式棧（重要）

思路

程式碼實現

執行過程詳解

解法三：Morris 遍歷（空間優化）

思路

程式碼實現

Morris 遍歷視覺化

解法四：顏色標記法（創新解法）

思路

程式碼實現

變化題型

1. 返回第 k 小的元素

2. 驗證二叉搜索樹

3. 中序遍歷的迭代器

4. 恢復二叉搜索樹

常見錯誤與陷阱

錯誤 1：結果列表作為參數傳遞

錯誤 2：迭代法忘記處理右子樹

錯誤 3：Morris 遍歷沒有恢復樹結構

錯誤 4：遞迴沒有基本情況

複雜度分析

相關題目推薦

實戰技巧總結

1. 遞迴模板

2. 迭代模板

3. 調試技巧

4. 完整測試用例

進階思考

1. 統一三種遍歷的迭代寫法

2. 線索二叉樹

總結

練習建議