从前序与中序遍历序列构造二叉树

这是一道围绕树、二叉树、数组展开的高频练习。建议先掌握「递归分治」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。

树

二叉树

数组

原题练习

题目分析

这道题表面上是在处理「从前序与中序遍历序列构造二叉树」，但先要想清楚题目到底让你返回什么，以及过程中哪些约束必须一直满足。从题型上看，它主要在考树、二叉树这些能力。先别急着写代码，先把题目要求翻译成人话，明确结果是什么、约束是什么、过程里要持续维护什么。只有先把题目要求翻译成人话，后面的推荐代码才是在实现思路，而不是直接给答案。

接下来怎么看推荐代码：带着这个理解再看推荐代码时，重点观察这条主线：前序遍历的第一个元素是根节点，再借助中序遍历把左右子树范围切开，递归构建即可。

推荐代码

推荐解法：递归分治

时间复杂度： O(n)

空间复杂度： O(n)

核心思路：前序遍历的第一个元素是根节点，再借助中序遍历把左右子树范围切开，递归构建即可。

class Solution {
    private Map<Integer, Integer> indexMap = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            indexMap.put(inorder[i], i);
        }
        return build(preorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode build(int[] preorder, int preLeft, int preRight, int inLeft, int inRight) {
        if (preLeft > preRight) {
            return null;
        }

        int rootValue = preorder[preLeft];
        TreeNode root = new TreeNode(rootValue);
        int inorderIndex = indexMap.get(rootValue);
        int leftSize = inorderIndex - inLeft;

        root.left = build(preorder, preLeft + 1, preLeft + leftSize, inLeft, inorderIndex - 1);
        root.right = build(preorder, preLeft + leftSize + 1, preRight, inorderIndex + 1, inRight);

        return root;
    }
}

结构化讲解

面试时怎么讲

开场思路

这题我会用递归分治，前序定根，中序切边界。

核心过程

前序区间第一个元素就是当前子树根节点。
在中序数组里找到根的位置，就能得到左右子树大小。
根据左子树大小切出新的前序和中序区间。
递归构建左右子树，区间为空时返回空节点。

复杂度总结

时间复杂度 O(n)，空间复杂度 O(n)。

面试补一句：这题最值得强调的是“前序定根，中序分边界”。

核心思路

这题的关键是把两种遍历的职责拆开看。前序负责告诉你“谁是根”，中序负责告诉你“左子树和右子树的边界在哪里”。

步骤讲解

用前序数组确定根节点

当前前序区间的第一个值，一定是这棵子树的根。

为什么这样做：前序遍历顺序就是根、左、右。

对应代码提示：int rootValue = preorder[preLeft];

用中序位置切分左右子树

根在中序中的位置左边是左子树，右边是右子树。

为什么这样做：中序遍历顺序是左、根、右，边界天然清晰。

对应代码提示：int inorderIndex = indexMap.get(rootValue);

递归构建左右子树

根据左子树大小计算前序和中序的左右区间，再分别递归。

为什么这样做：每个子问题都和原问题同构，只是区间变小。

对应代码提示：root.left = build(...); root.right = build(...);

易错点

每次在线性扫描中序找根

这样会让总复杂度退化到 O(n^2)。

正确理解：预先把中序值映射到下标，做到 O(1) 定位。

前序区间右边界计算错

左子树长度一旦算错，左右子树都会串位。

正确理解：先算 leftSize = inorderIndex - inLeft，再推导区间。

复杂度与适用判断

时间复杂度：O(n)

空间复杂度：O(n)

比其他方案更好在哪里：比先切数组再递归更高效，避免了频繁复制子数组。

适用判断：遍历序列重建树时，优先考虑区间递归和哈希定位。

额外提醒

真正的难点不是递归，而是把区间边界推导准确。