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

class Solution {
    int postIndex;
    int[] inOrder;
    int[] postOrder;
    Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.inOrder = inorder;
        this.postOrder = postorder;
        postIndex = postorder.length - 1;
        int idx = 0;
        //建立（元素，下标）键值对的哈希表
        for (int val : inorder) {
            map.put(val, idx++);
        }
        return helper(0, postorder.length - 1);
    }
    public TreeNode helper(int left, int right) {
        if (left>right){
            return null;
        }
        int rootVal = postOrder[postIndex--];
        TreeNode root = new TreeNode(rootVal);
        // 根据root所在的位置分成左右子树
        int index = map.get(rootVal);
        // 先执行右节点，与上面“postOrder[postIndex--]”匹配
        // 之前不理解，现在这样得到上面的root之后先递归执行右子节点，就解释上面的“postOrder[postIndex--]”
        root.right = helper(index+1,right);
        root.left = helper(left,index-1);
        return root;
    }
}