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

题目链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

代码

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
    if (preorder.length === 0) return null;
    const val = preorder[0];
    const root = new TreeNode(val);
    const index = inorder.indexOf(val);

    root.left = buildTree(preorder.slice(1, index + 1), inorder.slice(0, index));
    root.right = buildTree(preorder.slice(index + 1), inorder.slice(index + 1));
    return root;
};

function buildTree2(preorder: number[], inorder: number[]): TreeNode | null {
    function dfs(preStart: number, preEnd: number, inStart: number, inEnd: number): TreeNode | null {
        if (preEnd < preStart) return null;
        const val = preorder[preStart];
        const root = new TreeNode(val);
        const index = inorder.indexOf(val);
        const leftSize = index - inStart;

        root.left = dfs(preStart + 1, preStart + leftSize, inStart, index - 1);
        root.right = dfs(preStart + leftSize + 1, preEnd, index + 1, inEnd);

        return root
    }

    return dfs(0, preorder.length - 1, 0, inorder.length - 1);
};

思路

利用前序遍历和中序遍历的特性递归构建二叉树：

前序和中序遍历的特点

• 前序遍历：根节点 -> 左子树 -> 右子树
• 中序遍历：左子树 -> 根节点 -> 右子树

方法一：递归 + 数组切片

1. 前序遍历的第一个元素是根节点
2. 在中序遍历中找到根节点的位置 index
3. 中序遍历中，index 左边是左子树，右边是右子树
4. 递归构建左右子树：
   • 左子树：前序遍历 [1, index+1)，中序遍历 [0, index)
   • 右子树：前序遍历 [index+1, end)，中序遍历 [index+1, end)

方法二：递归 + 索引优化

使用索引代替数组切片，避免额外的空间开销：

1. 使用四个指针标记前序和中序遍历的范围
2. 通过 leftSize = index - inStart 计算左子树的节点数
3. 递归时传递索引范围而不是切片数组

关键点

• 前序遍历的第一个元素总是当前子树的根节点
• 通过中序遍历确定左右子树的边界
• 方法一简洁但有额外的切片开销，方法二更高效
• 时间复杂度 $O(n)$，空间复杂度 $O(n)$（递归栈）