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

◎

本节目标

用前序根节点和中序位置拆分半开区间，线性时间重建二叉树。

这道题是构造与二叉搜索树中“遍历关系确定结构”的代表。

查看 LeetCode 原题

题意与约束

节点值互不相同。前序遍历的第一个节点总是当前子树根；根在中序遍历中的位置将当前中序区间分成左右两部分，因此树可被唯一重建。

半开区间拆分

递归同时维护前序与中序的半开区间。若前序区间为空，当前子树为空。根值为 preorder[preLeft]；借助中序位置表得到 rootIndex 后，左子树大小为 rootIndex - inLeft。据此可直接计算两棵子树的四个边界，不需要创建任何切片数组。

正确性依据

当前前序首元素是根。中序中根左侧恰好是左子树全部节点，数量确定后，前序中紧随根的同样数量节点也恰好属于左子树；余下节点属于右子树。递归对两个更小区间应用同一关系，空区间停止，因此重建树的两种遍历都与输入一致。

代码实现

C++

C++17

#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
private:
    TreeNode* build(
        const vector<int>& preorder,
        int preLeft,
        int preRight,
        int inLeft,
        int inRight,
        const unordered_map<int, int>& inorderIndex
    ) {
        if (preLeft >= preRight) {
            return nullptr;
        }

        const int rootValue = preorder[preLeft];
        const int rootIndex = inorderIndex.at(rootValue);
        const int leftSize = rootIndex - inLeft;
        TreeNode* root = new TreeNode(rootValue);
        root->left = build(
            preorder,
            preLeft + 1,
            preLeft + 1 + leftSize,
            inLeft,
            rootIndex,
            inorderIndex
        );
        root->right = build(
            preorder,
            preLeft + 1 + leftSize,
            preRight,
            rootIndex + 1,
            inRight,
            inorderIndex
        );
        return root;
    }

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        unordered_map<int, int> inorderIndex;
        for (int i = 0; i < static_cast<int>(inorder.size()); i++) {
            inorderIndex[inorder[i]] = i;
        }
        return build(
            preorder,
            0,
            static_cast<int>(preorder.size()),
            0,
            static_cast<int>(inorder.size()),
            inorderIndex
        );
    }
};

Python

Python 3

from typing import Optional


class Solution:
    def buildTree(self, preorder: list[int], inorder: list[int]) -> Optional[TreeNode]:
        inorder_index = {value: index for index, value in enumerate(inorder)}

        def build(pre_left: int, pre_right: int, in_left: int, in_right: int) -> Optional[TreeNode]:
            if pre_left >= pre_right:
                return None

            root_value = preorder[pre_left]
            root_index = inorder_index[root_value]
            left_size = root_index - in_left
            root = TreeNode(root_value)
            root.left = build(pre_left + 1, pre_left + 1 + left_size, in_left, root_index)
            root.right = build(pre_left + 1 + left_size, pre_right, root_index + 1, in_right)
            return root

        return build(0, len(preorder), 0, len(inorder))

复杂度分析

位置表建立与每个节点构造各进行一次，时间复杂度为 O(n)。位置表和递归栈分别使用 O(n) 与 O(h) 额外空间。

易错点

• 在线性扫描中序数组寻找根，最坏退化为 O(n²)。
• 左子树大小用错为 rootIndex，忘记减去当前中序左边界。
• 对每层递归复制前序或中序子数组，增加不必要的空间与时间。

模式迁移

中序与后序构造的边界推导相同，只是后序末元素为根。遇到其他由序列恢复结构的问题，也应先找能唯一确定分割位置的信息。