LeetCode 解題思路:94. Binary Tree Inorder Traversal(二叉樹的中序遍歷)
掌握二叉樹遍歷的核心:遞迴、迭代與 Morris 遍歷
目錄
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(鏈狀樹)
相關題目推薦
- LeetCode 144: Binary Tree Preorder Traversal - 前序遍歷
- LeetCode 145: Binary Tree Postorder Traversal - 後序遍歷
- LeetCode 102: Binary Tree Level Order Traversal - 層序遍歷
- LeetCode 98: Validate Binary Search Tree - 驗證BST
- LeetCode 230: Kth Smallest Element in a BST - BST第k小
- LeetCode 99: Recover Binary Search Tree - 恢復BST
- LeetCode 173: Binary Search Tree Iterator - BST迭代器
實戰技巧總結
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 相關問題
- 樹的序列化與反序列化
- 表達式樹的計算
記住:樹的遍歷是解決樹問題的基礎,務必熟練掌握!