72.从前序与中序遍历序列构造二叉树
题目
给定两个整数数组 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 <= 3000
- inorder.length == preorder.length
- -3000 <= preorder[i], inorder[i] <= 3000
- preorder 和 inorder 均 无重复 元素
- inorder 均出现在 preorder
- preorder 保证 为二叉树的前序遍历序列
- inorder 保证 为二叉树的中序遍历序列
思路
前序遍历: 访问顺序是根 --> 左子树 --> 右子树
中序遍历: 访问顺序是左子树 --> 根 --> 右子树
规律一: 前序遍历的第一个元素，一定是整棵树的根
因为前序是 “根 --> 左 --> 右”，开头第一个是根。
例子里preroder=[3,....]，所以根就是3.
规律二: 在中序遍历里找到根，那根的左边全是左子树，右边全是右子树
因为中序是 “左 --> 根 --> 右”，根把中序序列天然切成两半，根的左边都属于左子树，根的右边都属于右子树。
例子里inorder = [9,3,15,20,7]，根3在中间。
所以我们一下就知道了: 根的左子树有一个节点(就是9)，根的右子树有3个节点(15、20、7)
有了这两条规律，重建过程就是一个天然的递归:
- 拿前序的第一个元素当根
- 在中序里定位到这个根，切成左右两部分，从而知道左、右子树各有多少个节点
-
根据左子树的节点数量，把前序剩下的部分也切成两段:
- 第一段是左子树的前序
- 后面是右子树的前序 前序数组本身分不出左右子树的界线，但"左子树有几个节点"这个数量是从中序数组算出来的。知道了这个数量（比如 1 个），就在前序里"根后面数出这么多个"当左子树，剩下的当右子树。 4. 递归的用左子树的前序 + 左子树的中序构建左子树，用右子树的前序 + 右子树的中序构建右子树
-
把构建好的左右子树挂到跟上，返回根。
class Solution {
fun buildTree(preorder: IntArray, inorder: IntArray): TreeNode? {
// base case：没有节点可构建，返回 null
if (preorder.isEmpty()) {
return null
}
// 1. 前序第一个元素是根
val rootVal = preorder[0]
val root = TreeNode(rootVal)
// 2. 在中序里找到根的位置，它左边是左子树，右边是右子树
val rootIndexInInorder = inorder.indexOf(rootVal)
// 左子树的节点个数 = 中序里根左边元素的数量
val leftSize = rootIndexInInorder
// 3. 切分中序：根左边是左子树中序，根右边是右子树中序
val leftInorder = inorder.copyOfRange(0, rootIndexInInorder)
val rightInorder = inorder.copyOfRange(rootIndexInInorder + 1, inorder.size)
// 4. 切分前序：根之后的 leftSize 个是左子树前序，再往后是右子树前序
val leftPreorder = preorder.copyOfRange(1, 1 + leftSize)
val rightPreorder = preorder.copyOfRange(1 + leftSize, preorder.size)
// 5. 递归构建左右子树，挂到根上
root.left = buildTree(leftPreorder, leftInorder)
root.right = buildTree(rightPreorder, rightInorder)
return root
}
}
进阶: 索引 + 哈希表 面试推荐
优点:
- 不复制数组，改用下标范围(起止索引)来表示当前处理的是哪一段
这是改进版最核心、也最需要转变思路的地方。
直观版是真的把数组切成小块（物理上复制出新数组）。改进版换个思路：我不复制数组，始终用原来那两个大数组，只是用几个"下标"来标记'我现在关心的是哪一段'。
打个比方：
直观版：像用剪刀把一长条纸真的剪成好几小段，每段单独拿在手里。 改进版：纸不剪，就用两根手指按住"从第几个到第几个"，告诉别人"我现在只看这一段"。手指一移，就表示换了一段，纸本身从头到尾没动过。 所以改进版的递归函数，参数不再是"小数组"，而是四个下标：前序的起止 [preStart, preEnd]、中序的起止 [inStart, inEnd]，用它们圈定"当前正在处理的是哪一段"。
- 用哈希表预存中序里每个值的位置，把indexOf的O(n)查找变成O(1)
既然每次都要在中序里找某个值的位置，那我一开始就把"每个值 → 它在中序的下标"全部记到一张哈希表里。以后要找根的位置，直接查表，O(1) 瞬间拿到，不用再一个个比对。
// 预处理：中序里每个值对应的下标，存进哈希表
val inorderIndexMap = HashMap
{ 9→0, 3→1, 15→2, 20→3, 7→4 } 以后想知道根 20 在中序哪个位置，直接 inorderIndexMap[20] 就得到 3，不用遍历。
class Solution {
// 哈希表：值 → 它在中序数组里的下标，O(1) 定位根的位置
private lateinit var inorderIndexMap: HashMap<Int, Int>
private lateinit var preorder: IntArray
fun buildTree(preorder: IntArray, inorder: IntArray): TreeNode? {
this.preorder = preorder
// 预处理：记录中序里每个值的下标
inorderIndexMap = HashMap()
for (i in inorder.indices) {
inorderIndexMap[inorder[i]] = i
}
// 用下标范围递归构建整棵树
return build(0, preorder.size - 1, 0, inorder.size - 1)
}
/**
* 用前序区间 [preStart, preEnd] 和中序区间 [inStart, inEnd] 构建子树
*/
private fun build(preStart: Int, preEnd: Int, inStart: Int, inEnd: Int): TreeNode? {
// base case：区间无效，说明没有节点
if (preStart > preEnd) {
return null
}
// 1. 前序区间的第一个元素是根
val rootVal = preorder[preStart]
val root = TreeNode(rootVal)
// 2. 在中序里 O(1) 定位根，算出左子树节点数
val rootIndex = inorderIndexMap[rootVal]!!
val leftSize = rootIndex - inStart
// 3. 递归构建左子树：
// 前序区间：根后面的 leftSize 个 → [preStart+1, preStart+leftSize]
// 中序区间：根左边 → [inStart, rootIndex-1]
root.left = build(preStart + 1, preStart + leftSize, inStart, rootIndex - 1)
// 4. 递归构建右子树：
// 前序区间：剩下的 → [preStart+leftSize+1, preEnd]
// 中序区间：根右边 → [rootIndex+1, inEnd]
root.right = build(preStart + leftSize + 1, preEnd, rootIndex + 1, inEnd)
return root
}
}
复杂度
版本一（切分子数组）：
- 时间 O(n²)：每层递归有 indexOf（O(n)）和数组复制（O(n)），最坏（退化成链）总共 O(n²)。
- 空间 O(n²)：不断复制子数组。
版本二（索引 + 哈希表）：
- 时间 O(n)：哈希表预处理 O(n)，之后每个节点只处理一次、O(1) 定位根，总共 O(n)。
- 空间 O(n)：哈希表 O(n) + 递归栈 O(h)。面试首选这个版本。
- 邮箱 ：charon.chui@gmail.com
- Good Luck!