从前序与中序遍历序列构造二叉树 题目描述 给定一棵二叉树的前序遍历 preorder 和中序遍历 inorder ，请构造二叉树并返回其根节点。假设二叉树中无重复元素。 示例： 输入：preorder = [ 3,9,20,15,7], inorder = [ 9,3,15,20,7 ] 输出：[ 3,9,20,null,null,15,7 ]（即根节点值为 3，左子树为 9，右子树为 20,15,7） 解题过程 步骤 1：理解前序和中序遍历的性质 前序遍历 ：[ 根节点] + [ 左子树的前序遍历] + [ 右子树的前序遍历 ] 中序遍历 ：[ 左子树的中序遍历] + [ 根节点] + [ 右子树的中序遍历 ] 关键点：前序遍历的第一个元素一定是整棵树的根节点。 步骤 2：定位根节点和左右子树区间 从前序遍历中取出第一个元素（如示例中的 3），作为根节点。 在中序遍历中找到该根节点的位置（示例中 inorder 的索引 1），其左侧是左子树的中序遍历（[ 9]），右侧是右子树的中序遍历（[ 15,20,7 ]）。 根据左子树的长度（此处为 1），在前序遍历中确定左右子树的边界： 左子树的前序遍历：根节点后的 1 个元素（[ 9 ]） 右子树的前序遍历：剩余元素（[ 20,15,7 ]） 步骤 3：递归构建左右子树 左子树：用左子树的前序遍历和中序遍历递归构建。 右子树：用右子树的前序遍历和中序遍历递归构建。 递归终止条件：当子树区间为空时返回 null。 步骤 4：示例推导 以 preorder = [ 3,9,20,15,7], inorder = [ 9,3,15,20,7 ] 为例： 根节点为 3。 在 inorder 中，左子树中序为 [ 9]，右子树中序为 [ 15,20,7 ]。 左子树前序为 [ 9]（对应 preorder[ 1:2]），右子树前序为 [ 20,15,7]（对应 preorder[ 2:5 ]）。 递归左子树：preorder=[ 9], inorder=[ 9 ] → 节点 9。 递归右子树：preorder=[ 20,15,7], inorder=[ 15,20,7 ]： 根节点 20，左子树中序 [ 15]，右子树中序 [ 7 ]； 左子树前序 [ 15]，右子树前序 [ 7 ] → 分别构建节点 15 和 7。 组合：根节点 3 的左子节点为 9，右子节点为 20；20 的左子节点为 15，右子节点为 7。 步骤 5：优化与边界处理 使用哈希表存储中序遍历的值到索引的映射，避免每次递归中线性查找根节点。 通过指针区间（而非复制数组）表示子树范围，减少空间开销。 总结 核心思路是利用前序定位根节点，中序划分左右子树，递归求解。时间复杂度 O(n)，空间复杂度 O(n)（哈希表与递归栈）。