106. 从中序与后序遍历序列构造二叉树：分治算法从底至上地构建二叉树.md

题目简述：

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

提示:

• inorder 和 postorder 都由 不同 的值组成

题目链接：106. 从中序与后序遍历序列构造二叉树

思路

这道题与 105. 从前序与中序遍历序列构造二叉树 挺像的。

先来研究一下中序遍历与后序遍历的特点。中序遍历的顺序是 “左 → 中 → 右”、后序遍历的 “左 → 右 → 中”。由于题干保证了无重复值节点，因此对于其中一个节点，我们可以利用中序遍历结果与后序遍历结果复原树的结构。

首先找到根节点，后序遍历结果集的最后一个元素即为根节点。将根节点视为初始的 “中” 节点。

后序遍历与先序遍历有个共同的特点，那就是 “中” 节点都是最先或最后被纳入结果集的。这意味着，在后序遍历结果集中 “中” 节点左侧的全部节点均为其子树节点——相比之下，中序遍历则没有这样的性质，其两侧既可能是其子树节点，也可能不是。

这样，只要我们的递归方法中既有中序遍历的范围索引、又有后序遍历的范围索引，先明确后序遍历范围的最后一个节点即为子树根节点，根据根节点值找到其在前序遍历结果集中的位置，那么用前序遍历子树区间的右端点减去前序遍历根节点索引的值就得到了左子树区间的长度，进而找到找到子树左右部分的分割，进而找到右子树区间。

针对每棵子树，我们都将其视为完整的树，递归这一过程，可以利用后序遍历结果集的性质得到新的根节点——新的根节点即为上一层递归根节点的直系子节点。

---

为了减少时间开销，可以提前将中序遍历结果集的值映射到索引，这样直接将索引与 “中” 节点的索引相比较，可以快速地判断出子树的节点属于左子树还是右子树。

代码

应同时将中序遍历的子树范围和后序遍历的子树范围作为参数。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {
    
    private HashMap<Integer, Integer> inorderMap;
    private int[] postorder;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.postorder = postorder;
        inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        return buildSubtree(0, inorder.length - 1, postorder.length - 1);
    }

    private TreeNode buildSubtree(int inStart, int inEnd, int postEnd) {
        if (inStart > inEnd || postEnd < 0) {
            return null;
        }

        TreeNode root = new TreeNode(postorder[postEnd]);
        int rootIndex = inorderMap.get(root.val);
        int leftSize = rootIndex - inStart;

        root.left = buildSubtree(inStart, rootIndex - 1, postEnd - (inEnd - rootIndex) - 1);
        root.right = buildSubtree(rootIndex + 1, inEnd, postEnd - 1);

        return root;
    }
}