从前序与中序遍历序列构造二叉树
Construct Binary Tree from Preorder and Inorder Traversal
给定同一棵二叉树的先序与中序序列，把树重新构造出来并返回根节点。
在力扣中练习题目描述
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1] 输出: [-1]
提示:
1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorder和inorder均 无重复 元素inorder均出现在preorderpreorder保证 为二叉树的前序遍历序列inorder保证 为二叉树的中序遍历序列
解题思路
分治 · 哈希表定位根
先序定根，中序定左右子树的边界
先序首项能确定根，但只知道根还无法分出左右子树。中序把“左子树、根、右子树”排在一起，因此根的中序位置能给出左子树的准确长度。
自拟主例 preorder=[8,4,6,12,10,15]，inorder=[4,6,8,10,12,15]，得到 [8,4,12,null,6,10,15]。根 8 左侧有两个节点，因此先序紧随其后的 4、6 属于左子树。
先建立值到中序下标的映射。图中的浅色空位还没有节点。
递归始终维护两段左闭右开区间。设根位置为 k，左子树长度就是 k-inL；先序的左右起点也必须按这个长度同步移动，不能仅凭数值大小划分。
先序首项 4 为根，中序位置 0，左子树 0 个节点。
- leftSize
- 0
4 的左区间为空，所以 6 是它的右孩子。空区间直接返回空指针，其余位置分别递归创建并接回根。哈希表预存中序位置，避免每层重新线性查找。
易错点
- leftSize 写成 k - inL + 1，把根也算进左子树，左子树会多一个节点、右子树少一个。
- 先序区间忘记跳过根，左子树递归时又把根建了一遍。
- 空区间判断和区间开闭混用：这里统一左闭右开，终止条件是 preL >= preR，不是 preL > preR。
分治 · 线性找根
不开哈希表，每次在 inorder 里扫出根的位置
结果正确，但每层线性查根最坏需要 O(n²)；主解法用哈希表避免重复查找。
连哈希表都不要，直接在 inorder 里从 inL 往后扫，扫到等于 rootVal 的位置就是 k。
其余逻辑一字不差：切区间、递归、挂孩子。区别只在于每找一次根都要扫一段中序。
最坏情况是树退化成一条向左的链：每次找根都要把整段中序扫完，第 i 层扫 O(n - i) 个元素，总和 O(n²)。树比较平衡时，每一层的扫描长度按子问题规模折半，总代价接近 O(n log n)。
所以这不是「错」的写法，而是把 O(1) 的查表换回了线性扫描。面试时先写它、再补一句「加个哈希表就能做到 O(n)」，是很自然的加分路径。
- 1preIdx 指向当前该用的先序元素，初始为 0。
- 2build(inL, inR)：区间为空返回 nullptr。
- 3取出 pre[preIdx++] 作为根，在 inorder 中从 inL 线性找到它的位置 k。
- 4递归建左右子树，preIdx 全程只向前走。
易错点
- 把 preIdx 按值传递，递归返回后游标不前进，整段先序会被反复使用。
- 先建右子树再建左子树：先序的顺序是「根 → 左 → 右」，顺序反了 preIdx 就对不上。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
preorder = [8,4,6,12,10,15], inorder = [4,6,8,10,12,15]先建立值到中序下标的映射。图中的浅色空位还没有节点。
查看 C++ 代码
延伸阅读
- 先序 + 中序、后序 + 中序都能唯一确定一棵树（106 是后序版，根在区间末尾）。
- 先序 + 后序不行：某个节点只有一个孩子时，无法判断这个孩子是左还是右。
- 「值互不相同」是这套下标切分的前提；有重复值时 pos 存不下唯一位置，题目会变成另一道题。