lc-889

给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。

如果存在多个答案，您可以返回其中 任何 一个。

示例 1：

输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]

示例 2:

输入: preorder = [1], postorder = [1]
输出: [1]

提示：

• 1 <= preorder.length <= 30
• 1 <= preorder[i] <= preorder.length
• preorder 中所有值都 不同
• postorder.length == preorder.length
• 1 <= postorder[i] <= postorder.length
• postorder 中所有值都 不同
• 保证 preorder 和 postorder 是同一棵二叉树的前序遍历和后序遍历

//leetcode submit region begin(Prohibit modification and deletion)
/**
 * 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 {
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        return createSubTree(preorder, postorder, 0, preorder.length - 1, 0, postorder.length - 1);
    }


    private TreeNode createSubTree(int[] preorder, int[] postorder, int preStart, int preEnd, int postStart, int postEnd) {
        if (preStart > preEnd || postStart > postEnd) {
            return null;
        }
        if (preStart == preEnd && postEnd == postStart) {
            return new TreeNode(preorder[preStart]);
        }

        int root = preorder[preStart];
        int leftRootIndex = preStart + 1;
        int leftPostEnd = 0;
        for (int i = postStart; i <= postEnd; i++) {
            if (postorder[i] == preorder[leftRootIndex]) {
                leftPostEnd = i;
                break;
            }
        }
        int len = leftPostEnd - postStart;
        return new TreeNode(root, createSubTree(preorder, postorder, leftRootIndex, leftRootIndex + len, postStart, postStart + len),
                createSubTree(preorder, postorder, leftRootIndex + len + 1, preEnd, postStart + len + 1, postEnd - 1));
    }
}
//leetcode submit region end(Prohibit modification and deletion)