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

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

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]
示例 2:
输入：inorder = [-1], postorder = [-1]
输出：[-1]

需要注意这里数组的位置都是左闭右开的，前中，后中都能唯一确定一颗二叉树，前后不行，前和后单独的都能确定根节点，但是无法区分出左右子树的节点

	public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length == 0 || postorder.length == 0)
            return null;
        return buildHelper(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    private TreeNode buildHelper(int[] inorder, int inorderStart, int inorderEnd, int[] postorder, int postorderStart,
            int postorderEnd) {
        if (postorderStart == postorderEnd)
            return null;
        int rootVal = postorder[postorderEnd - 1];
        TreeNode root = new TreeNode(rootVal);

        // 寻找根节点在中序数组中的位置
        int middleIndex;
        for (middleIndex = inorderStart; middleIndex < inorderEnd; middleIndex++) {
            if (inorder[middleIndex] == rootVal)
                break;
        }

        // 中序数组中 左中序的起始位置 和 右中序的起始位置
        int leftInorderStart = inorderStart;
        int leftInorderEnd = middleIndex;
        int rightInorderStart = middleIndex + 1;
        int rightInorderEnd = inorderEnd;

        // 后序数组中 左后序的起始位置 和 右后序的起始位置
        int leftPostOrderStart = postorderStart;
        int leftPostOrderEnd = leftPostOrderStart + (leftInorderEnd - leftInorderStart);
        int rightPostOrderStart = leftPostOrderEnd;
        int rightPostOrderEnd = postorderEnd - 1;

        root.left = buildHelper(inorder, leftInorderStart, leftInorderEnd, postorder, leftPostOrderStart,
                leftPostOrderEnd);
        root.right = buildHelper(inorder, rightInorderStart, rightInorderEnd, postorder, rightPostOrderStart,
                rightPostOrderEnd);
        return root;
    }