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

题目链接 · 灵神原题解（署名来源）

前序遍历：按照「根-左子树-右子树」的顺序遍历二叉树。

中序遍历：按照「左子树-根-右子树」的顺序遍历二叉树。

我们来看看示例 1 是怎么生成这棵二叉树的。

递归边界：如果 $preorder$ 的长度是 $0$ ，对应着空节点，返回空。

晕递归的同学推荐先看这期视频：深入理解递归【基础算法精讲 09】

写法一

Python 解法1C++ 解法1

python

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder:  # 空节点
            return None
        left_size = inorder.index(preorder[0])  # 左子树的大小
        left = self.buildTree(preorder[1: 1 + left_size], inorder[:left_size])
        right = self.buildTree(preorder[1 + left_size:], inorder[1 + left_size:])
        return TreeNode(preorder[0], left, right)

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
    // 用 span 可以避免拷贝，不用 span 的写法见【C++ 写法二】
    TreeNode* build(span<int> preorder, span<int> inorder) {
        if (preorder.empty()) { // 空节点
            return nullptr;
        }
        int left_size = ranges::find(inorder, preorder[0]) - inorder.begin(); // 左子树的大小
        TreeNode* left = build(preorder.subspan(1, left_size), inorder.subspan(0, left_size));
        TreeNode* right = build(preorder.subspan(1 + left_size), inorder.subspan(1 + left_size));
        return new TreeNode(preorder[0], left, right);
    }

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return build(preorder, inorder);
    }
};

C++ 解法3

cpp

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.empty()) { // 空节点
            return nullptr;
        }
        int left_size = ranges::find(inorder, preorder[0]) - inorder.begin(); // 左子树的大小
        vector<int> pre1(preorder.begin() + 1, preorder.begin() + 1 + left_size);
        vector<int> pre2(preorder.begin() + 1 + left_size, preorder.end());
        vector<int> in1(inorder.begin(), inorder.begin() + left_size);
        vector<int> in2(inorder.begin() + 1 + left_size, inorder.end());
        TreeNode* left = buildTree(pre1, in1);
        TreeNode* right = buildTree(pre2, in2);
        return new TreeNode(preorder[0], left, right);
    }
};

复杂度分析

时间复杂度： $O (n^{2})$ ，其中 $n$ 为 $preorder$ 的长度。最坏情况下二叉树是一条链，我们需要递归 $O (n)$ 次，每次都需要 $O (n)$ 的时间查找 $preorder [0]$ 和复制数组。
空间复杂度： $O (n^{2})$ 。

写法二

上面的写法有两个优化点：

用一个哈希表（或者数组）预处理 $inorder$ 每个元素的下标，这样就可以 $O (1)$ 查到 $preorder [0]$ 在 $inorder$ 的位置，从而 $O (1)$ 知道左子树的大小。
把递归参数改成子数组下标区间（左闭右开区间）的左右端点，从而避免复制数组。

Python 解法4C++ 解法4

python

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

        # 根据 preorder[pre_l:pre_r] 和 inorder[in_l:in_r] 生成二叉树，其中 in_r 没用到，可以省略
        def dfs(pre_l: int, pre_r: int, in_l: int) -> Optional[TreeNode]:
            if pre_l == pre_r:  # 空节点
                return None
            left_size = index[preorder[pre_l]] - in_l  # 左子树的大小
            left = dfs(pre_l + 1, pre_l + 1 + left_size, in_l)
            right = dfs(pre_l + 1 + left_size, pre_r, in_l + 1 + left_size)
            return TreeNode(preorder[pre_l], left, right)

        return dfs(0, len(preorder), 0)  # 左闭右开区间

cpp

// C++ 版待补充

C++ 解法5

cpp

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        unordered_map<int, int> index;
        for (int i = 0; i < n; i++) {
            index[inorder[i]] = i;
        }

        // 根据 preorder 的子数组 [pre_l,pre_r) 和 inorder 的子数组 [in_l,in_r) 生成二叉树，其中 in_r 没用到，可以省略
        auto dfs = [&](this auto&& dfs, int pre_l, int pre_r, int in_l) -> TreeNode* {
            if (pre_l == pre_r) { // 空节点
                return nullptr;
            }
            int left_size = index[preorder[pre_l]] - in_l; // 左子树的大小
            TreeNode* left = dfs(pre_l + 1, pre_l + 1 + left_size, in_l);
            TreeNode* right = dfs(pre_l + 1 + left_size, pre_r, in_l + 1 + left_size);
            return new TreeNode(preorder[pre_l], left, right);
        };
        return dfs(0, n, 0); // 左闭右开区间
    }
};

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 为 $preorder$ 的长度。递归 $O (n)$ 次，每次只需要 $O (1)$ 的时间。
空间复杂度： $O (n)$ 。

注：由于哈希表常数比数组大，实际运行效率可能不如写法一。

构造系列

这三题都可以用本文讲的套路解决。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

写法一 ​

复杂度分析 ​

写法二 ​

复杂度分析 ​

构造系列 ​

分类题单 ​

写法一

复杂度分析

写法二

复杂度分析

构造系列

分类题单