LeetCode 105: Construct Binary Tree from Preorder and Inorder Traversal (Index Map + Recursion)
LeetCode 105Binary TreeRecursionToday we solve LeetCode 105 - Construct Binary Tree from Preorder and Inorder Traversal.
Source: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
English
Problem Summary
Given preorder and inorder traversal arrays of the same binary tree (all values unique), rebuild and return the original tree root.
Key Insight
In preorder, the first value is always the root of current subtree. In inorder, that root splits left subtree values and right subtree values. Recursively apply this split.
Brute Force and Limitations
A direct recursive solution can linearly scan inorder each time to find root position. That works but becomes O(n^2) in skewed cases.
Optimal Algorithm Steps
1) Build a hashmap from value to inorder index.
2) Keep a global preorder pointer preIdx.
3) Recursive function build(l, r) returns subtree for inorder range [l, r].
4) Pick preorder[preIdx++] as root value, split by inorder index mid.
5) Build left subtree on [l, mid-1], then right subtree on [mid+1, r].
Complexity Analysis
Time: O(n) with index map lookup.
Space: O(n) for map + recursion stack (worst skewed tree).
Common Pitfalls
- Using preorder pointer incorrectly (increment timing wrong).
- Building right subtree before left subtree (breaks preorder consumption order).
- Forgetting boundary stop condition l > r.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int preIdx = 0;
private Map<Integer, Integer> pos = new HashMap<>();
private int[] preorder;
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
for (int i = 0; i < inorder.length; i++) {
pos.put(inorder[i], i);
}
return build(0, inorder.length - 1);
}
private TreeNode build(int l, int r) {
if (l > r) return null;
int rootVal = preorder[preIdx++];
TreeNode root = new TreeNode(rootVal);
int mid = pos.get(rootVal);
root.left = build(l, mid - 1);
root.right = build(mid + 1, r);
return root;
}
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func buildTree(preorder []int, inorder []int) *TreeNode {
pos := make(map[int]int, len(inorder))
for i, v := range inorder {
pos[v] = i
}
preIdx := 0
var build func(int, int) *TreeNode
build = func(l, r int) *TreeNode {
if l > r {
return nil
}
rootVal := preorder[preIdx]
preIdx++
root := &TreeNode{Val: rootVal}
mid := pos[rootVal]
root.Left = build(l, mid-1)
root.Right = build(mid+1, r)
return root
}
return build(0, len(inorder)-1)
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right)
* : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int preIdx = 0;
unordered_map<int, int> pos;
vector<int> pre;
TreeNode* buildTree(vector<int>& preo, vector<int>& inorder) {
pre = preo;
for (int i = 0; i < (int)inorder.size(); ++i) {
pos[inorder[i]] = i;
}
return build(0, (int)inorder.size() - 1);
}
TreeNode* build(int l, int r) {
if (l > r) return nullptr;
int rootVal = pre[preIdx++];
TreeNode* root = new TreeNode(rootVal);
int mid = pos[rootVal];
root->left = build(l, mid - 1);
root->right = build(mid + 1, r);
return root;
}
};# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def buildTree(self, preorder, inorder):
pos = {v: i for i, v in enumerate(inorder)}
pre_idx = 0
def build(l, r):
nonlocal pre_idx
if l > r:
return None
root_val = preorder[pre_idx]
pre_idx += 1
root = TreeNode(root_val)
mid = pos[root_val]
root.left = build(l, mid - 1)
root.right = build(mid + 1, r)
return root
return build(0, len(inorder) - 1)/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
var buildTree = function(preorder, inorder) {
const pos = new Map();
for (let i = 0; i < inorder.length; i++) {
pos.set(inorder[i], i);
}
let preIdx = 0;
function build(l, r) {
if (l > r) return null;
const rootVal = preorder[preIdx++];
const root = new TreeNode(rootVal);
const mid = pos.get(rootVal);
root.left = build(l, mid - 1);
root.right = build(mid + 1, r);
return root;
}
return build(0, inorder.length - 1);
};中文
题目概述
给定同一棵二叉树的前序遍历和中序遍历数组（元素值互不重复），重建并返回根节点。
核心思路
前序的第一个值一定是当前子树根节点；在中序里找到它的位置后，左侧就是左子树，右侧就是右子树。递归分治即可。
暴力解法与不足
朴素写法每次在线性扫描中序数组找根位置，会导致最坏 O(n^2)。
最优算法步骤
1）先建立 value -> inorderIndex 哈希表。
2）维护全局前序指针 preIdx。
3）定义递归 build(l, r)，表示构造中序区间 [l, r] 的子树。
4）取 preorder[preIdx++] 作为根，利用哈希表得到中序分割点 mid。
5）先递归构造左子树 [l, mid-1]，再构造右子树 [mid+1, r]。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(n)（哈希表 + 递归栈，最坏链状树）。
常见陷阱
- 前序指针递增时机错误。
- 先构造右子树会破坏前序消费顺序。
- 忘记 l > r 的递归终止条件。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int preIdx = 0;
private Map<Integer, Integer> pos = new HashMap<>();
private int[] preorder;
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
for (int i = 0; i < inorder.length; i++) {
pos.put(inorder[i], i);
}
return build(0, inorder.length - 1);
}
private TreeNode build(int l, int r) {
if (l > r) return null;
int rootVal = preorder[preIdx++];
TreeNode root = new TreeNode(rootVal);
int mid = pos.get(rootVal);
root.left = build(l, mid - 1);
root.right = build(mid + 1, r);
return root;
}
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func buildTree(preorder []int, inorder []int) *TreeNode {
pos := make(map[int]int, len(inorder))
for i, v := range inorder {
pos[v] = i
}
preIdx := 0
var build func(int, int) *TreeNode
build = func(l, r int) *TreeNode {
if l > r {
return nil
}
rootVal := preorder[preIdx]
preIdx++
root := &TreeNode{Val: rootVal}
mid := pos[rootVal]
root.Left = build(l, mid-1)
root.Right = build(mid+1, r)
return root
}
return build(0, len(inorder)-1)
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right)
* : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int preIdx = 0;
unordered_map<int, int> pos;
vector<int> pre;
TreeNode* buildTree(vector<int>& preo, vector<int>& inorder) {
pre = preo;
for (int i = 0; i < (int)inorder.size(); ++i) {
pos[inorder[i]] = i;
}
return build(0, (int)inorder.size() - 1);
}
TreeNode* build(int l, int r) {
if (l > r) return nullptr;
int rootVal = pre[preIdx++];
TreeNode* root = new TreeNode(rootVal);
int mid = pos[rootVal];
root->left = build(l, mid - 1);
root->right = build(mid + 1, r);
return root;
}
};# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def buildTree(self, preorder, inorder):
pos = {v: i for i, v in enumerate(inorder)}
pre_idx = 0
def build(l, r):
nonlocal pre_idx
if l > r:
return None
root_val = preorder[pre_idx]
pre_idx += 1
root = TreeNode(root_val)
mid = pos[root_val]
root.left = build(l, mid - 1)
root.right = build(mid + 1, r)
return root
return build(0, len(inorder) - 1)/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
var buildTree = function(preorder, inorder) {
const pos = new Map();
for (let i = 0; i < inorder.length; i++) {
pos.set(inorder[i], i);
}
let preIdx = 0;
function build(l, r) {
if (l > r) return null;
const rootVal = preorder[preIdx++];
const root = new TreeNode(rootVal);
const mid = pos.get(rootVal);
root.left = build(l, mid - 1);
root.right = build(mid + 1, r);
return root;
}
return build(0, inorder.length - 1);
};
Comments