Construct Binary Tree from Preorder and Postorder Traversal

Return any binary tree that matches the given preorder and postorder traversals.

Values in the traversals 

pre

 and 

post

 are distinct positive integers.

Example 1:

Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]
           

思路：總體思想跟inorder的那兩題很類似，但是這裡因為是binary tree，沒有大小的區分，隻有相對位置，那麼，這題跟上面兩題的差別就是如何不用current來找leftsize，

Preorder: current, left, right : 1, (2, 4, 5 ), (3,6,7) 

Postorder: left, right, current: (4,5,2), (6,7,3), 1

那麼破題口是在2上面，pre[pstart + 1] 在postorder 裡面是left的最後一個index，進而可以根據這個算出leftsize

注意要判斷pstart == pend的情況；

/**
 * 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[] pre, int[] post) {
        if(pre == null || post == null) {
            return null;
        }
        int n = pre.length;
        return build(pre, 0, n - 1, post, 0, n - 1);
    }
    
    private TreeNode build(int[] pre, int preStart, int preEnd, 
                           int[] post, int postStart, int postEnd) {
        if(preStart > preEnd || postStart > postEnd) {
            return null;
        }
        if(preStart == preEnd) {
            return new TreeNode(pre[preStart]);
        }
        TreeNode root = new TreeNode(pre[preStart]);
        int i = postStart;
        for(; i <= postEnd; i++) {
            if(post[i] == pre[preStart + 1]) {
                break;
            }
        }
        int leftlen = i - postStart + 1;
        root.left = build(pre, preStart + 1, preStart + leftlen,
                         post, postStart, i);
        root.right = build(pre, preStart + leftlen + 1, preEnd,
                          post, i + 1, postEnd - 1);
        return root;
    }
}