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;
    }
}