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

写在前面

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

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

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

---

Tag

【递归】【二叉树】

---

题目来源

106. 从中序与后序遍历序列构造二叉树

---

题目解读

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

---

解题思路

方法一：递归

前言

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

二叉树的中序遍历过程：

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

二叉树的后续遍历过程：

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

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

思路

根据后续遍历的顺序可知，后续遍历数组的最后一个元素为根节点。

于是可以根据后续遍历数组中的根节点定位到中序遍历中的根节点，接着可以将前序遍历数组分为左子树、根、右子树三部分，针对左子树和右子树这两个部分可以利用递归来完成二叉树的构造。

算法

我们需要查找后续遍历中的元素在中序遍历中的位置，为了高效查找，利用一个哈希表 idx_map 来记录中序遍历中元素的位置。

接着定义递归函数 helper(in_left, in_right) 表示在中序遍历的当前范围内（中序遍历的 [in_left, in_right]）递归构造二叉树，递归入口为 helper(0, n - 1)：

• 递归出口：如果 in_left > in_right，说明子树为空，返回空节点；
• 选择后续遍历的最后一个节点作为根节点；
• 在哈希表 idx_map 中查询根节点在中序遍历中的 idx。从 in_left 到 idx - 1 数属于左子树，从 idx + 1 到 in_right 属于右子树；
• 根据后续遍历逻辑，递归创建右子树 helper(idx + 1, in_right) 和左子树 helper(in_left, idx - 1)。
• 最后返回根节点 root。

注意：在递归创建子树的时候，先创建右子树，再创建左子树。因为在后续遍历中是先存储左子树的节点，再存储右子树的节点，最后存储根节点，如果每次选择「后续遍历的最后一个节点」为根节点，则先被构造出来的应该为右子树。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    int root_idx;
    unordered_map<int, int> idx_map;
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        root_idx = postorder.size() - 1;
        // 建立哈希表
        int idx = 0;
        for (auto val : inorder) {
            idx_map[val] = idx++;
        }

        function<TreeNode*(int, int)> helper = [&](int in_left, int in_right) -> TreeNode* {
            if (in_left > in_right) {
                return nullptr;
            }

            // 选择 后续遍历数组的最后一个元素作为当前子树的根节点
            int root_val = postorder[root_idx--];
            TreeNode* root = new TreeNode(root_val);

            // 根据 root_val 所在位置分为左右两棵子树
            int idx = idx_map[root_val];

            // 递归构建右子树 
            root->right = helper(idx + 1, in_right);
            // 递归构建左子树
            root->left = helper(in_left, idx - 1);
            return root;
        };
        return helper(0, inorder.size() - 1);
    }
};

复杂度分析

时间复杂度：$O(n)$，$n$ 为数中节点个数。

空间复杂度：$O(n)$。

---

写在最后

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

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

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