MediumRating 1660
106. Construct Binary Tree from Inorder and Postorder Traversal
arrayhash-tabledivide-and-conquertreebinary-tree
解題說明
Construct Binary Tree from Inorder and Postorder Traversal
題目描述：給定一棵二元樹的中序走訪陣列 inorder 和後序走訪陣列 postorder（保證樹中無重複值），請重建並返回該二元樹的根節點。
解題思路：
利用後序走訪的關鍵特性：後序陣列的最後一個元素永遠是當前子樹的根節點。知道根節點後，再利用中序走訪的特性——根節點將中序陣列切分為左子樹和右子樹——即可遞迴地重建整棵樹。
- 從後序陣列的末端取出根節點：
postorder[postEnd]即為當前子樹的根。 - 在中序陣列中定位根節點：利用預先建好的雜湊表（
unordered_map<int, int>），以 O(1) 找到根在中序陣列中的索引inMid。 - 計算左子樹的節點數量：
leftSize = inMid - inStart。 - 遞迴建立左子樹和右子樹：
- 左子樹的中序範圍：
[inStart, inMid - 1]；後序範圍：[postStart, postStart + leftSize - 1]。 - 右子樹的中序範圍：
[inMid + 1, inEnd]；後序範圍：[postStart + leftSize, postEnd - 1]。
- 左子樹的中序範圍：
- 返回根節點。
使用雜湊表將中序查詢從 O(n) 降至 O(1)，整體時間複雜度為 O(n)。
C++ 解法
複雜度分析
時間複雜度：O(n) — 建立雜湊表需 O(n)；之後每個節點只被遞迴函式處理一次（每次呼叫建立一個節點），共 n 次呼叫，每次查詢雜湊表為 O(1)，整體 O(n)。
空間複雜度：O(n) — 雜湊表儲存 n 個元素需 O(n)；遞迴呼叫堆疊深度在最壞情況（退化為單鏈）為 O(n)，平衡樹則為 O(log n)。
虛擬碼
1. Build a hash map: inorderIndex[value] = index for all elements in inorder. 2. Call build(inorder, postorder, inStart=0, inEnd=n-1, postStart=0, postEnd=n-1). 3. In build(inStart, inEnd, postStart, postEnd): a. If inStart > inEnd, return null. b. rootVal = postorder[postEnd]. c. Create a new TreeNode with rootVal. d. inMid = inorderIndex[rootVal]. e. leftSize = inMid - inStart. f. root.left = build(inStart, inMid-1, postStart, postStart+leftSize-1). g. root.right = build(inMid+1, inEnd, postStart+leftSize, postEnd-1). h. Return root.
其他解法
方法一：線性掃描（不用雜湊表）
每次在中序陣列中用線性掃描找根節點位置，不需要額外空間建立雜湊表。時間複雜度退化為 O(n²)（每層遞迴掃描一次），空間複雜度 O(n)（遞迴堆疊）。適合題目保證 n 很小的情形，但一般情況下效率不佳。
方法二：迭代 + 明確堆疊模擬
使用明確的堆疊（stack<TreeNode*>）和反向走訪後序陣列（從尾端往前相當於前序的鏡像），搭配中序陣列指標進行迭代重建。時間複雜度 O(n)，空間複雜度 O(n)。此方法避免了系統遞迴堆疊溢位的風險，適合 n 極大的情形，但實作較複雜。
延伸思考
- 若已知前序走訪（preorder）和中序走訪（inorder），如何重建二元樹（LeetCode 105）？根節點的定位規則有何不同？
- 如果樹中允許重複值，僅憑中序和後序走訪，能否唯一確定一棵二元樹？為什麼？
- 在本題的遞迴解法中，若 n = 10^5 且樹退化為單鏈（skewed tree），遞迴深度也達到 10^5，可能導致堆疊溢位。請問如何將遞迴解改寫為迭代解以避免此問題？