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

根据一棵树的中序遍历与后序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

例如，给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树：

解题思路

膜拜大佬：图解构造二叉树之中序+后序

前提

解决此问题的关键在于要很熟悉树的各种遍历次序代表的什么，最好能够将图画出来。本题解带你先进行中序遍历和后续遍历二叉树，然后再根据遍历结果将二叉树进行还原。

首先，来一棵树

然后再看树的遍历结果

根据中序和后序遍历结果还原二叉树

中序遍历和后续遍历的特性

首先来看题目给出的两个已知条件 中序遍历序列 和 后序遍历序列 根据这两种遍历的特性我们可以得出两个结论

在后序遍历序列中,最后一个元素为树的根节点
在中序遍历序列中,根节点的左边为左子树，根节点的右边为右子树

如下图所示

树的还原过程描述

根据中序遍历和后续遍历的特性我们进行树的还原过程分析

首先在后序遍历序列中找到根节点(最后一个元素)
根据根节点在中序遍历序列中找到根节点的位置
根据根节点的位置将中序遍历序列分为左子树和右子树
根据根节点的位置确定左子树和右子树在中序数组和后续数组中的左右边界位置
递归构造左子树和右子树
返回根节点结束

树的还原过程变量定义

需要定义几个变量帮助我们进行树的还原

unordered_map inorderMap 需要一个哈希表来保存中序遍历序列中,元素和索引的位置关系.因为从后序序列中拿到根节点后，要在中序序列中查找对应的位置,从而将数组分为左子树和右子树
int ri 根节点在中序遍历数组中的索引位置
中序遍历数组的两个位置标记 [is, ie]，is 是起始位置，ie是结束位置
后序遍历数组的两个位置标记 [ps, pe] ps 是起始位置，pe 是结束位置

位置关系的计算

在找到根节点位置以后，我们要确定下一轮中，左子树和右子树在中序数组和后续数组中的左右边界的位置。

左子树-中序数组 is = is, ie = ri - 1
左子树-后序数组 ps = ps, pe = ps + ri - is - 1 (pe计算过程解释，后续数组的起始位置加上左子树长度-1 就是后后序数组结束位置了，左子树的长度 = 根节点索引-左子树)
右子树-中序数组 is = ri + 1, ie = ie
右子树-后序数组ps = ps + ri - is, pe - 1

听不明白没关系，看图就对了,计算图示如下

树的还原过程

代码

C++

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int value) : val(value), left(nullptr), right(nullptr) {}
};

//递归
class Solution {
public:
    unordered_map<int,int> inorderMap;
    vector<int> post;
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        for (int i = 0; i < inorder.size(); i++) {
            // 将中序遍历的节点值和索引记录在哈希表中
            inorderMap.insert(pair<int,int>(inorder[i],i));
        }
        post = postorder; //
        TreeNode* root = getTree(0, inorder.size() - 1, 0, postorder.size() - 1);
        return root;
    }
    /**
     * 根据边界构建树
     * @param is inorderStart
     * @param ie inorderEnd
     * @param ps postorderStart
     * @param pe postorderEnd
     * @return
     */
    TreeNode* getTree(int is, int ie, int ps, int pe){
        if (is > ie || ps > pe) return nullptr;
        int nodeVal = post[pe]; // 根据后序遍历的结果取得根节点
        //int ri = inorderMap.find(nodeVal)->second; // 用下面一条语句也许
        int ri = inorderMap[nodeVal]; // 得到 根节点 在中序遍历数组中的下标。
        TreeNode* node = new TreeNode(nodeVal);
        node->left = getTree(is, ri - 1, ps, ps + ri - 1 -is);
        node->right = getTree(ri + 1, ie, ps + ri - is, pe - 1);
        // 注意 返回的是新建立的 node 节点
        return node;
    }
};

JavaScript

//构造函数
function TreeNode(val, left, right) {
    this.val = (val === undefined ? 0 : val);
    this.left = (left === undefined ? null : left);
    this.right = (right === undefined ? null : right);
}

let inorderMap = {};
let post = [];
/**
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var buildTree = function(inorder, postorder) {
    for (let i = 0; i < inorder.length; i++) {
        // 将中序遍历的节点值和索引记录在哈希表中
        inorderMap[inorder[i]] = i;
    }
    post = postorder;
    return getTree(0, inorder.length - 1, 0, postorder.length - 1);
};

var node1 = buildTree([4, 2, 8, 5, 9, 1, 6, 10, 3, 7], [4, 8, 9, 5, 2, 10, 6, 7, 3, 1]);
console.log(node1);

/**
 * 根据边界构建树
 * @param is inorderStart
 * @param ie inorderEnd
 * @param ps postorderStart
 * @param pe postorderEnd
 * @return {TreeNode}
 */
function getTree(is, ie, ps, pe) {
    if (is > ie || ps > pe) return null;
    let nodeVal = post[pe];
    let ri = inorderMap[nodeVal];
    let node = new TreeNode(nodeVal);
    //let node = { val: nodeval }; // 没有用构造函数，直接是对象
    node.left = getTree(is, ri - 1, ps, ps + ri - 1 - is);
    node.right = getTree(ri + 1, ie, ps + ri - is, pe - 1);
    return node;
}