【算法入门&二叉树】从先中后序的遍历到用中后序列构造二叉树|如何抵挡递归法该死的魅力（下

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
    int post_idx;
    unordered_map<int, int> idx_map;
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param inorder int整型vector 中序遍历序列
     * @param postorder int整型vector 后序遍历序列
     * @return TreeNode类
     */
    TreeNode* helper(int in_left,int in_right,vector<int>& inorder,vector<int>& postorder){
        if(in_left>in_right){
            return nullptr;
        }
        // 选择 post_idx 位置的元素作为当前子树根结点
        int root_val = postorder[post_idx];
        TreeNode* root = new TreeNode(root_val);
        // 根据 root 所在位置分成左右两棵子树
        int index = idx_map[root_val];
        // 下标减一
        post_idx--;
        // 构造右子树
        root->right=helper(index + 1, in_right, inorder, postorder);
        // 构造左子树
        root->left=helper(in_left, index - 1, inorder, postorder);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        // 从后序遍历的最后一个元素开始，是先序根结点
        post_idx = (int)postorder.size()-1;
        // 建立 map集合(值，键) 相反的
        int idx=0;
        for(auto &val : inorder){
            idx_map[val] = idx++;
        }
        return helper(0, post_idx, inorder, postorder);
    }
};