105. 从前序与中序遍历序列构造二叉树
题目描述
输入两个整数数组：preorder 是某棵二叉树的先序遍历结果，inorder 是同一棵树的中序遍历结果。
树中所有节点值各不相同。根据这两个序列还原出原来的二叉树，返回它的根节点。
返回的树按层序数组表示，null 代表空位。
示例 1
输入：preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出：[3,9,20,null,null,15,7]
解释：先序第一个值 3 是根；它在中序中左边只有 9，右边是 15,20,7，据此递归即可还原。
示例 2
输入：preorder = [-1], inorder = [-1] 输出：[-1]
解释：只有一个节点。
数据范围
1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000- 两个数组中都没有重复值。
inorder中的每个值也都在preorder中出现。- 输入一定是同一棵二叉树合法的先序和中序遍历。
解题思路：递归 + 哈希表
前序游标依次提供根；用中序值到下标映射划分左右区间，先构造左侧再右侧。
为什么正确
每次 build(lo,hi) 消耗恰好对应中序该区间的前序节点。
复杂度分析
时间 O(n)，哈希表 O(n)，递归栈 O(h)，输出 O(n)。使用索引范围，无 Python 切片复制；h 为树高，最坏为 n，Python 深链递归可能触及解释器深度限制，应改用显式栈。
易错点
前序必须先消费左子树再消费右子树；区间不能包含已经选作根的中序位置。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def buildTree(self, preorder, inorder):
positions = {value: i for i, value in enumerate(inorder)}
cursor = 0
def build(lo, hi):
nonlocal cursor
if lo > hi:
return None
value = preorder[cursor]
cursor += 1
mid = positions[value]
root = TreeNode(value)
root.left = build(lo, mid - 1)
root.right = build(mid + 1, hi)
return root
return build(0, len(inorder) - 1)class Solution {
private Map<Integer, Integer> positions;
private int cursor;
private int[] preorder;
public TreeNode buildTree(int[] preorder, int[] inorder) {
positions = new HashMap<>();
for (int i = 0; i < inorder.length; i++) positions.put(inorder[i], i);
cursor = 0;
this.preorder = preorder;
return build(0, inorder.length - 1);
}
private TreeNode build(int lo, int hi) {
if (lo > hi) {
return null;
}
int value = preorder[cursor];
cursor++;
int mid = positions.get(value);
TreeNode root = new TreeNode(value);
root.left = build(lo, mid - 1);
root.right = build(mid + 1, hi);
return root;
}
}class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
unordered_map<int, int> positions;
for (int i = 0; i < (int)inorder.size(); i++) positions[inorder[i]] = i;
int cursor = 0;
function<TreeNode*(int, int)> build = [&](int lo, int hi) -> TreeNode* {
if (lo > hi) {
return nullptr;
}
int value = preorder[cursor];
cursor++;
int mid = positions[value];
TreeNode* root = new TreeNode(value);
root->left = build(lo, mid - 1);
root->right = build(mid + 1, hi);
return root;
};
return build(0, (int)inorder.size() - 1);
}
};func buildTree(preorder []int, inorder []int) *TreeNode {
positions := map[int]int{}
for i, value := range inorder {
positions[value] = i
}
cursor := 0
var build func(lo, hi int) *TreeNode
build = func(lo, hi int) *TreeNode {
if lo > hi {
return nil
}
value := preorder[cursor]
cursor++
mid := positions[value]
root := &TreeNode{Val: value}
root.Left = build(lo, mid-1)
root.Right = build(mid+1, hi)
return root
}
return build(0, len(inorder)-1)
}var buildTree = function(preorder, inorder) {
const positions = new Map(inorder.map((value, i) => [value, i]));
let cursor = 0;
const build = (lo, hi) => {
if (lo > hi) {
return null;
}
const value = preorder[cursor];
cursor++;
const mid = positions.get(value);
const root = new TreeNode(value);
root.left = build(lo, mid - 1);
root.right = build(mid + 1, hi);
return root;
};
return build(0, inorder.length - 1);
};function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
const positions = new Map<number, number>(inorder.map((value, i) => [value, i]));
let cursor = 0;
const build = (lo: number, hi: number): TreeNode | null => {
if (lo > hi) {
return null;
}
const value = preorder[cursor];
cursor++;
const mid = positions.get(value)!;
const root = new TreeNode(value);
root.left = build(lo, mid - 1);
root.right = build(mid + 1, hi);
return root;
};
return build(0, inorder.length - 1);
};其他解法
递归 + 哈希表按区间划分，最好理解；迭代法用栈模拟沿左链下行和回溯，省去哈希表和递归栈。
解法 2：迭代（栈） 时间 O(n)，空间 O(h)
栈里保存还没有确定右孩子的节点，中序指针 idx 指向下一个应当“回溯”的节点。依次读前序值：栈顶值不等于 inorder[idx] 时，新节点是栈顶的左孩子。相等时不断出栈并右移 idx，新节点是最后一个出栈节点的右孩子。新节点总是入栈。
不需要哈希表，也没有递归，深链树不会栈溢出。规则不直观，要先理解前序沿左链下行、中序标记回溯点这层关系。
class Solution:
def buildTree(self, preorder, inorder):
if not preorder:
return None
root = TreeNode(preorder[0])
stack = [root]
idx = 0
for value in preorder[1:]:
node = stack[-1]
if node.val != inorder[idx]:
node.left = TreeNode(value)
stack.append(node.left)
else:
while stack and stack[-1].val == inorder[idx]:
node = stack.pop()
idx += 1
node.right = TreeNode(value)
stack.append(node.right)
return rootclass Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0) return null;
TreeNode root = new TreeNode(preorder[0]);
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
int idx = 0;
for (int i = 1; i < preorder.length; i++) {
TreeNode node = stack.peek();
if (node.val != inorder[idx]) {
node.left = new TreeNode(preorder[i]);
stack.push(node.left);
} else {
while (!stack.isEmpty() && stack.peek().val == inorder[idx]) {
node = stack.pop();
idx++;
}
node.right = new TreeNode(preorder[i]);
stack.push(node.right);
}
}
return root;
}
}class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (preorder.empty()) return nullptr;
TreeNode* root = new TreeNode(preorder[0]);
vector<TreeNode*> stack{root};
int idx = 0;
for (int i = 1; i < (int)preorder.size(); i++) {
TreeNode* node = stack.back();
if (node->val != inorder[idx]) {
node->left = new TreeNode(preorder[i]);
stack.push_back(node->left);
} else {
while (!stack.empty() && stack.back()->val == inorder[idx]) {
node = stack.back();
stack.pop_back();
idx++;
}
node->right = new TreeNode(preorder[i]);
stack.push_back(node->right);
}
}
return root;
}
};func buildTree(preorder []int, inorder []int) *TreeNode {
if len(preorder) == 0 {
return nil
}
root := &TreeNode{Val: preorder[0]}
stack := []*TreeNode{root}
idx := 0
for i := 1; i < len(preorder); i++ {
node := stack[len(stack)-1]
if node.Val != inorder[idx] {
node.Left = &TreeNode{Val: preorder[i]}
stack = append(stack, node.Left)
} else {
for len(stack) > 0 && stack[len(stack)-1].Val == inorder[idx] {
node = stack[len(stack)-1]
stack = stack[:len(stack)-1]
idx++
}
node.Right = &TreeNode{Val: preorder[i]}
stack = append(stack, node.Right)
}
}
return root
}var buildTree = function(preorder, inorder) {
if (!preorder.length) return null;
const root = new TreeNode(preorder[0]);
const stack = [root];
let idx = 0;
for (let i = 1; i < preorder.length; i++) {
let node = stack[stack.length - 1];
if (node.val !== inorder[idx]) {
node.left = new TreeNode(preorder[i]);
stack.push(node.left);
} else {
while (stack.length && stack[stack.length - 1].val === inorder[idx]) {
node = stack.pop();
idx++;
}
node.right = new TreeNode(preorder[i]);
stack.push(node.right);
}
}
return root;
};function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
if (!preorder.length) return null;
const root = new TreeNode(preorder[0]);
const stack: TreeNode[] = [root];
let idx = 0;
for (let i = 1; i < preorder.length; i++) {
let node = stack[stack.length - 1];
if (node.val !== inorder[idx]) {
node.left = new TreeNode(preorder[i]);
stack.push(node.left);
} else {
while (stack.length && stack[stack.length - 1].val === inorder[idx]) {
node = stack.pop()!;
idx++;
}
node.right = new TreeNode(preorder[i]);
stack.push(node.right);
}
}
return root;
};