106. Construct Binary Tree from Inorder and Postorder Traversal
題目 / Problem
中文：給定兩個整數陣列 inorder（中序遍歷結果）和 postorder（後序遍歷結果），它們來自同一棵二元樹。請你根據這兩個陣列重建出這棵二元樹，並回傳它的根節點。
English: You are given two integer arrays inorder and postorder, where inorder is the inorder traversal and postorder is the postorder traversal of the same binary tree. Reconstruct the tree and return its root node.
Constraints / 限制
- 1 <= inorder.length <= 3000
- postorder.length == inorder.length
- -3000 <= inorder[i], postorder[i] <= 3000
- All values are unique / 所有值皆不重複。
- Every value in postorder also appears in inorder, and both are valid traversals of the tree.
Worked example / 範例
inorder = [9, 3, 15, 20, 7]
postorder = [9, 15, 7, 20, 3]
Output = [3, 9, 20, null, null, 15, 7]
The tree looks like:
3
/ \
9 20
/ \
15 7
名詞解釋 / Glossary
- Binary tree / 二元樹：每個節點最多有兩個子節點（左子節點、右子節點）的樹狀結構。
- Inorder traversal / 中序遍歷：依「左子樹 → 根 → 右子樹」的順序拜訪所有節點。關鍵性質：根節點會把中序陣列切成「左邊全是左子樹、右邊全是右子樹」。
- Postorder traversal / 後序遍歷：依「左子樹 → 右子樹 → 根」的順序拜訪。關鍵性質：最後一個元素永遠是整棵（子）樹的根。
- Recursion / 遞迴：函式呼叫自己，把大問題拆成同型的小問題（這裡是：建左子樹、建右子樹）。
- Hash map / 雜湊表：一種用「鍵」直接查「值」的容器，查詢平均 O(1)。這裡用它把「數值 → 在中序陣列的位置」記下來，避免每次線性搜尋。
- Subarray / 子陣列：用一對索引
[left, right]表示原陣列的一段連續區間，不需要真的複製資料。 - Global index / 全域索引：一個在遞迴過程中共用、會持續移動的指標，這裡用來從後尾往前掃
postorder。
思路
最直接的想法（暴力法）是：後序陣列的最後一個元素就是根，我們拿它去中序陣列裡找位置，位置左邊就是左子樹的中序、右邊就是右子樹的中序。知道左子樹有幾個節點後，也能在後序陣列裡切出左、右兩段，然後對左右兩段各自遞迴。這個想法本身就是正確解，但天真實作有兩個效率陷阱：一是每次都用線性搜尋在中序陣列裡找根，最壞會退化成 O(n²)；二是若每層都用真正的複製（slice）產生新子陣列，會浪費大量時間與記憶體。改良的關鍵是：先用一個雜湊表把「數值 → 中序索引」全部記下來，找根就變成 O(1)；同時只用索引區間 [inLeft, inRight] 來代表子陣列，完全不複製資料。還有一個漂亮的小技巧：如果我們從後往前讀後序陣列，順序會是「根 → 右子樹 → 左子樹」，所以只要維持一個全域指標從尾端往前走，並且先建右子樹、再建左子樹，就能自然對上這個順序，連在後序陣列裡計算切點都省了。每一步的不變量是：目前這段中序區間 [inLeft, inRight] 恰好對應目前後序指標所指的那棵子樹。
The brute-force idea is already the right idea: the last element of postorder is the root; find it in inorder, everything to its left is the left subtree's inorder and everything to its right is the right subtree's inorder, then recurse on both halves. Two things make a naive version slow: searching inorder linearly for each root degrades to O(n²), and physically slicing arrays at every level wastes time and memory. We fix the first with a hash map from value to its inorder index (root lookup becomes O(1)), and the second by passing index ranges [inLeft, inRight] instead of copying. There's also an elegant shortcut: read postorder from right to left and it reads as "root → right subtree → left subtree." So we keep one global pointer walking backward through postorder and build the right subtree before the left; the order lines up automatically and we never have to compute split points inside postorder. The invariant at every call is: the current inorder range [inLeft, inRight] is exactly the set of nodes belonging to the subtree whose root sits at the current postorder pointer.
逐步走查 / Walkthrough
Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3].
First build the value→inorder-index map: {9:0, 3:1, 15:2, 20:3, 7:4}.
Start postIdx = 4 (last index of postorder), and call build(inLeft=0, inRight=4).
| Step | postIdx | root value | inorder range [L,R] | root index in inorder | left range | right range | 說明 / note |
|---|---|---|---|---|---|---|---|
| 1 | 4 | 3 |
[0,4] | 1 | [0,0] | [2,4] | 根=3；先遞迴右邊 / recurse right first |
| 2 | 3 | 20 |
[2,4] | 3 | [2,2] | [4,4] | 3 的右子樹根=20 |
| 3 | 2 | 7 |
[4,4] | 4 | — | — | 20 的右子樹根=7，葉節點 / leaf |
| 4 | 1 | 15 |
[2,2] | 2 | — | — | 20 的左子樹根=15，葉節點 / leaf |
| 5 | 0 | 9 |
[0,0] | 0 | — | — | 3 的左子樹根=9，葉節點 / leaf |
Notice postIdx decreases by exactly 1 each time we create a node (5 nodes → 5 decrements), and building right-before-left is what makes the walk match postorder read backward. Final tree:
3
/ \
9 20
/ \
15 7
Solution — C
/*
* 演算法 / Algorithm:
* 後序陣列最後一個元素是根；在中序陣列中找到它，左邊是左子樹、右邊是右子樹。
* The last postorder element is the root; split inorder at it into left/right subtrees.
* 從後往前讀 postorder（根→右→左），先建右子樹再建左子樹，用雜湊表 O(1) 查根位置。
* Walk postorder backward, build right subtree before left, use a hash map for O(1) root lookup.
*/
// LeetCode 已定義好的節點結構（此處僅示意，實際由平台提供）/ node struct provided by LeetCode:
// struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; };
#include <stdlib.h> // malloc 記憶體配置 / for malloc
// 值域是 -3000..3000，共 6001 個可能值；用位移把值變成非負索引 / shift values into a non-negative array index
#define OFFSET 3000 // 把 -3000 對到 0 / maps -3000 to array slot 0
#define RANGE 6001 // 可能值的總數 / total number of distinct possible values
// 全域的「值 -> 中序索引」查表，取代 hash map；索引 = 值 + OFFSET / value -> inorder index lookup
static int inIndexOf[RANGE];
// 全域指標：目前後序陣列從尾端往前掃到哪裡 / global pointer scanning postorder from the back
static int postIdx;
// 記住 postorder 陣列的起點，遞迴中直接取用 / remember postorder base pointer for the recursion
static int *postArr;
// 遞迴建樹：負責中序區間 [inLeft, inRight] 這段所代表的子樹 / build subtree covering inorder[inLeft..inRight]
static struct TreeNode *build(int inLeft, int inRight) {
if (inLeft > inRight) // 區間為空 => 沒有節點 / empty range means no node here
return NULL; // 回傳空指標表示「沒有子樹」/ NULL = no subtree
int rootVal = postArr[postIdx]; // 目前後序指標指向的值就是這段的根 / current postorder value is this subtree's root
postIdx--; // 用掉一個根，指標往前一格 / consume it, move pointer left
// 配置一個新節點；malloc 回傳一塊未初始化的記憶體 / allocate one uninitialized node
struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
root->val = rootVal; // 設定節點值；-> 是「透過指標存取成員」/ set value; -> dereferences a pointer field
// 根在中序陣列的位置：O(1) 查表，避免線性搜尋 / root's position in inorder via O(1) lookup
int rootPos = inIndexOf[rootVal + OFFSET];
// 關鍵順序：先建右子樹！因為 postorder 反著讀是 根->右->左 / build RIGHT first (backward postorder = root,right,left)
root->right = build(rootPos + 1, inRight); // 右子樹的中序在根的右邊 / right subtree is to the right of root
root->left = build(inLeft, rootPos - 1); // 左子樹的中序在根的左邊 / left subtree is to the left of root
return root; // 回傳這棵（子）樹的根 / return this subtree's root
}
struct TreeNode *buildTree(int *inorder, int inorderSize,
int *postorder, int postorderSize) {
// 先把「每個中序值 -> 它的索引」記進查表 / record each inorder value's index into the lookup table
for (int i = 0; i < inorderSize; i++)
inIndexOf[inorder[i] + OFFSET] = i; // 值 + OFFSET 當作陣列下標 / value+OFFSET used as array subscript
postArr = postorder; // 讓遞迴函式能存取 postorder / expose postorder to the recursion
postIdx = postorderSize - 1; // 從最後一個元素開始（整棵樹的根）/ start at the last element (whole-tree root)
return build(0, inorderSize - 1); // 整段中序區間對應整棵樹 / full inorder range = whole tree
}
Solution — C++
/*
* 演算法 / Algorithm:
* postorder 最後一個元素是根；在 inorder 中切成左/右子樹並遞迴。
* The last postorder element is the root; split inorder into left/right and recurse.
* 反向掃 postorder（根→右→左），先建右子樹，用 unordered_map 做 O(1) 根查詢。
* Scan postorder backward (root,right,left), build right subtree first, O(1) lookup via unordered_map.
*/
#include <vector>
#include <unordered_map>
using namespace std;
// LeetCode 提供的節點定義 / node definition provided by LeetCode:
// struct TreeNode { int val; TreeNode *left; TreeNode *right;
// TreeNode(int x): val(x), left(nullptr), right(nullptr) {} };
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
// unordered_map 是雜湊表：value -> inorder 索引，查詢平均 O(1) / hash map: value -> inorder index
unordered_map<int, int> inIndex;
for (int i = 0; i < (int)inorder.size(); i++)
inIndex[inorder[i]] = i; // 記下每個值的位置 / record each value's position
int postIdx = (int)postorder.size() - 1; // 從尾端開始的指標 / pointer starting at the tail
// lambda：可遞迴的區域函式；捕捉 (&) 外部變數的參考以便修改 postIdx / recursive lambda capturing by reference
// 用 auto&& self 讓 lambda 能呼叫自己（C++ 遞迴 lambda 慣用寫法）/ self-reference trick for recursion
auto build = [&](auto&& self, int inLeft, int inRight) -> TreeNode* {
if (inLeft > inRight) // 空區間 => 沒有節點 / empty range => no node
return nullptr; // nullptr 表示空子樹 / nullptr = empty subtree
int rootVal = postorder[postIdx--]; // 取根後指標前移；post-decrement 先用值再減 / take root then move pointer left
TreeNode* root = new TreeNode(rootVal); // new 在堆上建立節點 / allocate node on the heap
int rootPos = inIndex[rootVal]; // O(1) 找到根在 inorder 的位置 / O(1) root position in inorder
// 先右後左，對應 postorder 反向讀取順序 / right before left, matching backward postorder
root->right = self(self, rootPos + 1, inRight); // 右子樹 / right subtree
root->left = self(self, inLeft, rootPos - 1); // 左子樹 / left subtree
return root; // 回傳子樹根 / return subtree root
};
return build(build, 0, (int)inorder.size() - 1); // 對整段中序建樹 / build over the full inorder range
}
};
複雜度 / Complexity
- Time: O(n) — 每個節點恰好被建立一次，且靠雜湊表把「找根位置」壓到 O(1)，所以總時間與節點數
n成線性。若改用線性搜尋找根，最壞會退化成 O(n²)。Each node is created exactly once and the root lookup is O(1) via the hash map, so total work is linear in the number of nodesn; a linear search for the root instead would degrade to O(n²). - Space: O(n) — 雜湊表存
n個項目佔 O(n)；遞迴呼叫堆疊最深為樹高，平衡樹是 O(log n)，最壞（退化成鏈狀）是 O(n)。回傳的樹本身不算額外空間。The hash map holdsnentries (O(n)); the recursion stack is as deep as the tree height — O(log n) when balanced, O(n) in the worst (skewed) case. The output tree itself is not counted as extra space.
Pitfalls & Edge Cases
- 左右建構順序 / Build order matters：因為我們反向讀 postorder（根→右→左），必須先建右子樹再建左子樹。若順序寫反，
postIdx會把節點指派到錯的子樹，樹整個錯掉。Because postorder is read backward, you must build the right subtree before the left; swapping them assigns nodes to the wrong side. - 共用指標的更新時機 / Shared pointer timing：
postIdx是共用狀態，必須在建子樹之前就先取出根值並遞減，不能延後，否則遞迴會讀到錯的值。Take the root and decrementpostIdxbefore recursing; deferring it corrupts every following read. - 空區間判斷 / Empty-range base case：
inLeft > inRight是遞迴終止條件，代表這裡沒有節點，回傳NULL/nullptr。少了它會無限遞迴或越界。TheinLeft > inRightcheck is the base case for a missing child; without it the recursion never stops. - 單節點輸入 / Single node：
[-1]這種只有一個節點的輸入，build(0,0)會建立根、兩邊都落到空區間，自然正確處理。A one-node input is handled naturally: the root is built and both children hit the empty case. - 負值當索引 / Negative values as indices（C 版）：C 版用陣列取代雜湊表，值域含負數，所以要
+OFFSET (3000)把值平移成非負下標，否則會越界存取。The C version shifts values by 3000 so negatives become valid array indices. - 重複值的假設 / Uniqueness assumption：本解法依賴「值唯一」才能用值當鍵查位置；題目保證唯一，但若值可能重複，這個對應關係就會失效。The value→index mapping only works because values are guaranteed unique.