题解 | #从中序与后序遍历序列构造二叉树#

// 通过后序遍历序列可以确定树的根节点，然后利用中序遍历将树分为左子树和右子树，递归地构建整棵树
#include <unordered_map>
#include <vector>
class Solution {
public:
    TreeNode* TreeHelper(vector<int>& inorder,int inStart, int inEnd, vector<int>& postorder, int postStart, int postEnd, unordered_map<int, int>& inorderIndexMap){
        if(inStart > inEnd  || postStart > postEnd){
            return nullptr;
        }
        int rootVal = postorder[postEnd];
        TreeNode* root = new TreeNode(rootVal);
        // 查找根节点在中序序列中的位置 利用哈希表的映射来查找
        int inRootIndex = inorderIndexMap[rootVal];
        // 左子树在中序序列中的长度
        int leftSize = inRootIndex - inStart;
        // 其中postStart + leftSize - 1 是后序遍历序列中的左子树位置
        root->left = TreeHelper(inorder, inStart, inRootIndex - 1, postorder, postStart, postStart + leftSize - 1, inorderIndexMap);
        root->right = TreeHelper(inorder, inRootIndex + 1, inEnd, postorder, postStart + leftSize, postEnd - 1, inorderIndexMap);
        return root;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        unordered_map<int, int> inorderIndexMap;
        for(int i = 0; i < inorder.size(); i ++){
            // 将中序序列中每个值映射到哈希表中
            inorderIndexMap[inorder[i]] = i;
        }
        return TreeHelper(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1, inorderIndexMap);
    }
};