105. Construct Binary Tree from Preorder and Inorder Traversal
題目 / Problem
中文：給你兩個整數陣列 preorder 和 inorder。preorder 是某棵二元樹的「前序遍歷」結果，inorder 是同一棵樹的「中序遍歷」結果。請你根據這兩個陣列，重建並回傳這棵二元樹。
English: You are given two integer arrays preorder and inorder, where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree. Construct and return that binary tree.
Constraints / 限制
- 1 <= preorder.length <= 3000
- inorder.length == preorder.length
- -3000 <= preorder[i], inorder[i] <= 3000
- preorder 和 inorder 中的值都是唯一的（no duplicates）。
- inorder 中每個值都出現在 preorder 裡（they contain the same set of values）。
- 保證 preorder 是合法的前序遍歷，inorder 是合法的中序遍歷。
Worked Example / 範例
Input: preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
這對應下面這棵樹 / This corresponds to the tree:
3
/ \
9 20
/ \
15 7
名詞解釋 / Glossary
- 二元樹 / Binary Tree：每個節點最多有兩個子節點（左子節點、右子節點）的樹狀資料結構。A tree where each node has at most two children: a
leftchild and arightchild. - 節點 / Node：樹的基本單位，這裡每個節點存一個整數值
val，以及指向左右子樹的指標left、right。The basic unit of a tree; here each node stores an integervaland two pointersleftandright. - 前序遍歷 / Preorder Traversal：走訪順序是「根 → 左子樹 → 右子樹」。所以
preorder的第一個元素一定是整棵樹的根。Visit order is root → left subtree → right subtree, so the first element ofpreorderis always the root. - 中序遍歷 / Inorder Traversal：走訪順序是「左子樹 → 根 → 右子樹」。因此在
inorder中，根節點左邊全是左子樹的值，右邊全是右子樹的值。Visit order is left subtree → root → right subtree; so ininordereverything left of the root belongs to the left subtree and everything right belongs to the right subtree. - 遞迴 / Recursion：函式呼叫自己來解決更小的子問題。這裡我們用遞迴分別建立左子樹和右子樹。A function calling itself to solve smaller sub-problems; we use it to build the left and right subtrees.
- 分治法 / Divide and Conquer：把大問題拆成獨立的小問題，各自解完再組合。Split a big problem into independent smaller ones, solve each, then combine.
- 雜湊表 / Hash Map：一種能用「值」在 O(1) 平均時間查到對應資訊的資料結構。這裡用來記錄「某個值在
inorder中的位置」，避免每次都線性搜尋。A structure giving average O(1) lookup; here it maps each value to its index ininorderso we don't scan repeatedly.
思路
我們先想最直接的做法：前序遍歷的第一個元素 preorder[0] 一定是整棵樹的根，因為前序是「根→左→右」。找到根之後，我們去中序陣列 inorder 裡找到這個根的位置。由於中序是「左→根→右」，根左邊的所有元素就是左子樹的中序，根右邊的所有元素就是右子樹的中序。假設左邊有 k 個元素，那麼左子樹就有 k 個節點；回到 preorder，根之後緊接著的 k 個元素就是左子樹的前序，剩下的就是右子樹的前序。這樣我們就把問題分成兩個一模一樣、但更小的子問題：用「左子樹的前序＋中序」建左子樹，用「右子樹的前序＋中序」建右子樹，然後把它們接到根上。這就是遞迴（分治）。基礎情況是：當某個區間為空時，回傳空節點（NULL）。若每次都用線性掃描去 inorder 裡找根的位置，最壞情況（例如樹退化成一條鏈）會是 O(n²)。優化的關鍵是：先用一個雜湊表把「每個值 → 它在 inorder 的索引」記下來，之後每次找根位置都是 O(1)，總複雜度就降到 O(n)。實作上，我們用索引範圍（preStart..preEnd、inStart..inEnd）來代表當前正在處理的子陣列，避免真的去複製陣列，節省空間與時間。
The most direct idea starts from a key fact: preorder[0] is always the root of the whole tree, because preorder visits root first. Once we know the root value, we locate it inside inorder. Because inorder is left → root → right, every element to the left of the root in inorder forms the left subtree and every element to the right forms the right subtree. If there are k elements on the left, the left subtree has exactly k nodes — so back in preorder, the k elements right after the root are the left subtree's preorder, and the rest are the right subtree's preorder. Now the problem splits into two identical but smaller problems: build the left subtree from its (preorder, inorder) slice, build the right subtree from its slice, then attach both to the root. That is recursion / divide and conquer, with the base case "empty range → return NULL". If we find the root's position by scanning inorder linearly every time, a skewed tree degrades to O(n²). The optimization: precompute a hash map from value → index in inorder, making each root lookup O(1) and the whole algorithm O(n). To avoid copying arrays, we pass around index ranges (preStart..preEnd, inStart..inEnd) that describe the current sub-arrays.
逐步走查 / Walkthrough
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7].
First build the index map from inorder / 先建中序索引表：
{9:0, 3:1, 15:2, 20:3, 7:4}.
We recurse with build(preStart, preEnd, inStart, inEnd). Below k = number of nodes in the left subtree = rootIndexInInorder - inStart.
| Step | preorder range | inorder range | root = pre[preStart] | root idx in inorder | left size k | 動作 / Action |
|---|---|---|---|---|---|---|
| 1 | pre[0..4]=[3,9,20,15,7] | in[0..4]=[9,3,15,20,7] | 3 | 1 | 1 | root=3；左子樹用 pre[1..1],in[0..0]；右子樹用 pre[2..4],in[2..4] |
| 2 (left of 3) | pre[1..1]=[9] | in[0..0]=[9] | 9 | 0 | 0 | root=9；左右皆空 → 葉節點 / leaf |
| 3 (right of 3) | pre[2..4]=[20,15,7] | in[2..4]=[15,20,7] | 20 | 3 | 1 | root=20；左子樹 pre[3..3],in[2..2]；右子樹 pre[4..4],in[4..4] |
| 4 (left of 20) | pre[3..3]=[15] | in[2..2]=[15] | 15 | 2 | 0 | root=15；左右皆空 → 葉 / leaf |
| 5 (right of 20) | pre[4..4]=[7] | in[4..4]=[7] | 7 | 4 | 0 | root=7；左右皆空 → 葉 / leaf |
Assembled tree / 組合結果：
3
/ \
9 20
/ \
15 7
輸出 [3,9,20,null,null,15,7]，正確 / matches expected output.
Solution — C
/*
* 演算法 / Algorithm:
* 前序第一個元素是根；在中序中找到根的位置，左邊是左子樹、右邊是右子樹。
* The first preorder element is the root; its position in inorder splits
* inorder into left/right subtrees. Recurse on index ranges (no array copying).
* 用雜湊表把「值 → 中序索引」預先記下，讓每次找根為 O(1)，總體 O(n)。
* A value→inorder-index hash map makes each root lookup O(1), giving O(n) total.
*/
// LeetCode 提供的樹節點定義（此處僅為說明，實際由平台給出）
// LeetCode-provided node struct (shown for reference):
struct TreeNode {
int val; // 節點存的整數 / the integer stored in this node
struct TreeNode *left; // 指向左子節點的指標 / pointer to the left child
struct TreeNode *right; // 指向右子節點的指標 / pointer to the right child
};
#include <stdlib.h> // 需要 malloc / needed for malloc
// 值的範圍是 -3000..3000，共 6001 個可能值。用陣列當雜湊表最簡單快速。
// Values range -3000..3000 (6001 possibilities); a plain array is the simplest, fastest map.
// 索引 = 值 + 3000（把負數平移成非負）/ index = value + 3000 (shift negatives into [0,6000]).
#define OFFSET 3000 // 平移量 / the shift amount
#define MAP_SIZE 6001 // 陣列大小 / size of the lookup array
// 遞迴輔助函式：用給定的索引範圍建一棵子樹。
// Recursive helper: build one subtree from the given index ranges.
// idxMap[v+OFFSET] = v 在 inorder 中的位置 / position of value v inside inorder.
static struct TreeNode* build(int* preorder, int preStart, int preEnd,
int inStart, int inEnd, int* idxMap) {
// 範圍為空表示沒有節點，回傳 NULL（空子樹）。
// An empty range means no node here → return NULL (empty subtree).
if (preStart > preEnd) {
return NULL;
}
// 前序的第一個元素就是這棵（子）樹的根值。
// The first element of this preorder slice is this subtree's root value.
int rootVal = preorder[preStart];
// 配置一個新節點；malloc 向系統要一塊記憶體，回傳指向它的指標。
// Allocate a new node; malloc requests memory and returns a pointer to it.
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = rootVal; // 設定節點值 / set the node's value
root->left = NULL; // 先設空，稍後可能覆寫 / default empty, may be overwritten
root->right = NULL; // 先設空 / default empty
// O(1) 從雜湊表查出根在中序中的位置。
// O(1) lookup of the root's position in inorder via the map.
int inRoot = idxMap[rootVal + OFFSET];
// 中序中根左邊的元素個數 = 左子樹的節點數。
// Number of elements left of the root in inorder = size of the left subtree.
int leftSize = inRoot - inStart;
// 建左子樹：前序取根之後的 leftSize 個元素；中序取根左邊那段。
// Build left subtree: preorder = the leftSize elements after root; inorder = left part.
root->left = build(preorder,
preStart + 1, preStart + leftSize, // 前序左子樹範圍 / preorder range
inStart, inRoot - 1, // 中序左子樹範圍 / inorder range
idxMap);
// 建右子樹：前序取剩下的元素；中序取根右邊那段。
// Build right subtree: preorder = remaining elements; inorder = right part.
root->right = build(preorder,
preStart + leftSize + 1, preEnd, // 前序右子樹範圍 / preorder range
inRoot + 1, inEnd, // 中序右子樹範圍 / inorder range
idxMap);
return root; // 回傳建好的（子）樹根 / return the built subtree root
}
// LeetCode 入口函式；簽名固定。preorderSize、inorderSize 是陣列長度。
// LeetCode entry function; fixed signature. preorderSize/inorderSize are array lengths.
struct TreeNode* buildTree(int* preorder, int preorderSize,
int* inorder, int inorderSize) {
// 空輸入直接回傳空樹（依約束不會發生，但保險起見）。
// Empty input → empty tree (won't happen per constraints, but safe to guard).
if (preorderSize == 0) {
return NULL;
}
// 建立「值 → 中序索引」的雜湊表。
// Build the value→inorder-index map.
// 用 malloc 配置陣列；每個 int 存一個索引 / allocate an int array to hold indices.
int* idxMap = (int*)malloc(sizeof(int) * MAP_SIZE);
// 掃一遍 inorder，把每個值的位置記進 idxMap。
// Scan inorder once, recording each value's position into idxMap.
for (int i = 0; i < inorderSize; i++) {
// inorder[i] + OFFSET 把值平移成合法陣列索引 / shift value to a valid index.
idxMap[inorder[i] + OFFSET] = i;
}
// 從整個陣列範圍開始遞迴建樹。
// Start recursion over the full index ranges.
struct TreeNode* root = build(preorder, 0, preorderSize - 1,
0, inorderSize - 1, idxMap);
// 釋放雜湊表記憶體，避免記憶體洩漏。
// Free the map memory to avoid a memory leak.
free(idxMap);
return root; // 回傳整棵樹的根 / return the whole tree's root
}
Solution — C++
/*
* 演算法 / Algorithm:
* preorder[0] 是根；在 inorder 找到它，左邊為左子樹、右邊為右子樹，遞迴建樹。
* preorder[0] is the root; locate it in inorder to split into left/right subtrees, recurse.
* 用 unordered_map 記「值→中序索引」讓查找 O(1)，總複雜度 O(n)。
* An unordered_map (value→inorder index) makes lookups O(1), giving O(n) overall.
*/
#include <vector>
#include <unordered_map>
using namespace std;
// LeetCode 的節點定義（此處僅供參考）/ LeetCode's node definition (for reference):
// struct TreeNode {
// int val;
// TreeNode *left;
// TreeNode *right;
// TreeNode() : val(0), left(nullptr), right(nullptr) {}
// TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
// };
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
// unordered_map 是雜湊表，平均 O(1) 查找 / hash map with average O(1) lookup.
// key = 值, value = 它在 inorder 的索引 / key = value, value = its index in inorder.
unordered_map<int, int> idxMap;
// range-for 逐一走訪 inorder 的索引 / range-based loop over inorder indices.
for (int i = 0; i < (int)inorder.size(); i++) {
idxMap[inorder[i]] = i; // 記錄每個值的位置 / record each value's position
}
// 從整個範圍開始遞迴建樹 / start recursion over the full ranges.
return build(preorder, 0, (int)preorder.size() - 1,
0, (int)inorder.size() - 1, idxMap);
}
private:
// 遞迴輔助函式：用索引範圍建一棵子樹 / recursive helper building one subtree by ranges.
// idxMap 以參考 (&) 傳入，避免複製整張表 / passed by reference (&) to avoid copying the map.
TreeNode* build(const vector<int>& preorder, int preStart, int preEnd,
int inStart, int inEnd, unordered_map<int, int>& idxMap) {
// 範圍為空 → 空子樹 / empty range → empty subtree.
if (preStart > preEnd) {
return nullptr;
}
// 前序第一個元素是根值 / first preorder element is the root value.
int rootVal = preorder[preStart];
// new 在堆積上建立節點並回傳指標 / new allocates a node on the heap, returns a pointer.
TreeNode* root = new TreeNode(rootVal);
// O(1) 查出根在中序的位置 / O(1) lookup of root's index in inorder.
int inRoot = idxMap[rootVal];
// 根左邊的元素個數 = 左子樹大小 / count left of root = size of left subtree.
int leftSize = inRoot - inStart;
// 建左子樹：前序取接下來 leftSize 個、中序取左段。
// Build left subtree: next leftSize preorder elements; left inorder segment.
root->left = build(preorder,
preStart + 1, preStart + leftSize,
inStart, inRoot - 1,
idxMap);
// 建右子樹：前序取其餘元素、中序取右段。
// Build right subtree: remaining preorder elements; right inorder segment.
root->right = build(preorder,
preStart + leftSize + 1, preEnd,
inRoot + 1, inEnd,
idxMap);
return root; // 回傳這棵子樹的根 / return this subtree's root
}
};
複雜度 / Complexity
- Time: O(n) —
n是節點數。建雜湊表掃一遍是 O(n)；每個節點在遞迴中剛好被當作「根」處理一次，且每次找根位置是 O(1)，所以總共是 O(n)。若不用雜湊表而每次線性掃inorder，最壞會退化成 O(n²)。 /nis the number of nodes. Building the map is O(n); each node becomes a root exactly once and its lookup is O(1), so O(n) total. Without the map, linear scans would make it O(n²) in the worst (skewed) case. - Space: O(n) — 雜湊表存
n個項目佔 O(n)；遞迴呼叫堆疊最深為樹的高度，最壞（鏈狀樹）為 O(n)，平衡時為 O(log n)。輸出的樹本身不計入額外空間。 / The map holdsnentries → O(n); the recursion stack goes as deep as the tree height, O(n) worst case (skewed) and O(log n) when balanced. The output tree itself isn't counted as extra space.
Pitfalls & Edge Cases
- 左子樹大小算錯 / Miscomputing
leftSize：必須用inRoot - inStart（相對於當前子區間的起點），不能用inRoot（絕對索引）。用絕對索引在右子樹遞迴時會切錯範圍。Must useinRoot - inStart(relative to the current sub-range's start), not the absoluteinRoot; the absolute value breaks the split once you recurse into right subtrees. - 前序範圍的邊界 / Preorder boundaries：左子樹是
preStart+1 .. preStart+leftSize，右子樹是preStart+leftSize+1 .. preEnd。off-by-one 是這題最常見的錯誤。These+1/+leftSizeoffsets are the classic off-by-one traps in this problem. - 忘記回傳 NULL 的基礎情況 / Missing the
NULLbase case：preStart > preEnd時必須回傳空，否則會無限遞迴或存取越界。Without the empty-range check the recursion never terminates and reads out of bounds. - 負值當索引 / Negative values as indices (C only)：值可為負，C 版用陣列雜湊表時要加
OFFSET（+3000）把值平移成非負索引，否則會越界寫入。In the C array-map, values can be negative, so addOFFSETbefore indexing; forgetting it corrupts memory. - 重複值假設 / Relying on uniqueness：本演算法依賴「值唯一」才能在
inorder中確定根的唯一位置。若有重複值這個方法就不成立——但題目已保證唯一。The approach depends on unique values to pin down the root's single position ininorder; guaranteed here. - 記憶體釋放 / Freeing memory (C)：C 版用
malloc建雜湊表後要free，避免洩漏；節點本身由 LeetCode 負責回收，不要提前free。Free the map youmalloc, but don't free the tree nodes — LeetCode owns those. - C++ 傳參用參考 / Pass the map by reference in C++：
unordered_map<int,int>& idxMap用&避免每次遞迴複製整張表（否則會退化成 O(n²) 時間與空間）。The&avoids copying the whole map on every recursive call.