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

文章目录

写在前面
Tag
题目来源
题目解读
解题思路
- 方法一：递归
写在最后

写在前面

本专栏专注于分析与讲解【面试经典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);
    }
};