【面试经典150 | 二叉树】从前序与中序遍历序列构造二叉树

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

• Tag：介绍本题牵涉到的知识点、数据结构；
• 题目来源：贴上题目的链接，方便大家查找题目并完成练习；
• 题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
• 解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
• 知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【递归】【迭代】【二叉树】

题目来源

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

题目解读

给你一棵二叉树的前序和中序遍历得到的两个数组，现在根据两个数组来构造二叉树。

解题思路

二叉树问题都可以使用递归和迭代两种方法来解决。

方法一：递归

前言

首先回忆一下二叉树的前序和中序遍历过程。

二叉树的前序遍历过程：

• 先遍历根节点；
• 接着递归遍历左子树；
• 最后递归遍历右子树。

二叉树的中序遍历过程：

• 先递归遍历左子树；
• 接着遍历根节点；
• 最后递归遍历右子树。

在「递归」遍历子树的过程中，我们也是将子树看成是一棵全新的树，按照相应的顺序进行遍历。

思路

根据上述提到的前序遍历顺序可以将 preorder 数组分为三部分，根、左子树、右子树。目前仅通过先序遍历的结果数组可以确定的是根节点值为 3。

中序遍历的结果数组可以分为三部分：左子树、根、右子树。

只要我们在中序遍历的结果数组中定位出根节点，那么就可以分别知道左子树和右子树的数目，进而可以定位出左、右子树的边界即在数组中的范围。这样就知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，就可以递归地对构造出左子树和右子树，再将这两棵子树接到根节点的左右位置。

在定位根节点的时候，利用哈希表来记录各个节点在数组中的位置，因为题目中事先说明了二叉树中节点的值不会出重复。哈希表中的键表示一个元素的值，值表示该键表示的值在中序遍历数组中的位置。

算法

class Solution {
private:
    int pre_idx;
    unordered_map<int, int> index_map;
public:
    TreeNode* slove(const vector<int>& preorder, const vector<int>& inorder, int in_left, int in_right) {
        if (in_left > in_right) {
            return nullptr;
        }
        // 前序遍历中的根节点
        int root_val = preorder[pre_idx++];
        // 建立根节点
        TreeNode* root = new TreeNode(root_val);
        // 在中序遍历中定位根节点
        int idx = index_map[root_val];
        
        // 递归构建左子树，需要左子树的先序、中序的边界
        root->left = slove(preorder, inorder, in_left, idx - 1);
        root->right = slove(preorder, inorder, idx + 1, in_right);
        return root;

    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = inorder.size();
        pre_idx = 0;
        // 构建哈希表，快速定位根节点
        for (int i = 0; i < n; ++i) {
            index_map[inorder[i]] = i;
        }
        return slove(preorder, inorder, 0, n-1);
    }
};

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 是树中的节点个数。

空间复杂度：$O(n)$。返回的答案需要 $O(n)$ 空间，通过不算作占用额外的空间；哈希表占用的额外空间为 $O(n)$；递归的栈空间最大为 $O(n)$。因此，总的空间复杂度为 $O(n)$。

写在最后

如果您发现文章有任何错误或者对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法，欢迎评论区交流。

最后，感谢您的阅读，如果有所收获的话可以给我点一个 👍 哦。