力扣 LeetCode 106. 从中序与后序遍历序列构造二叉树（Day9：二叉树）

解题思路：

前中后序

给前中和后中都可以确定唯一的一棵二叉树

前中：先前 后中

中后：先中 后后

注意区间，统一左闭右开比较好

终止条件： if (postorderStart == postorderEnd) return null;

class Solution {
    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);
    }

    public TreeNode buildHelper(int[] inorder, int inorderStart, int inorderEnd, int[] postorder, int postorderStart, int postorderEnd) {
        if (postorderStart == postorderEnd) return null;

        int rootValue = postorder[postorderEnd - 1];
        TreeNode root = new TreeNode(rootValue);
        int middleIndex = 0;
        for (middleIndex = 0; middleIndex < inorderEnd; middleIndex++) {
            if (inorder[middleIndex] == rootValue)
                break;
        }

        int leftInorderStart = inorderStart;
        int leftInorderEnd = middleIndex;
        int rightInorderStart = middleIndex + 1;
        int rightInorderEnd = inorderEnd;

        int leftPostorderStart = postorderStart;
        int leftPostorderEnd = postorderStart + (middleIndex - inorderStart);
        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;
    }
}