LeetCode 889. Construct Binary Tree from Preorder and Postorder Traversal

原题链接在这里：https://leetcode.com/problems/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]

Note:

• 1 <= pre.length == post.length <= 30
• pre[] and post[] are both permutations of 1, 2, ..., pre.length.
• It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.

题解：

The first element in pre, 1 is actually the root's val. 

The second element in pre, 2 is root's left child val. Find 2's index in post, before that, all are root left subtree.

Vice Versa.

Use a HashMap to store post element and its index for quick search.

In recursion, before using pre[preL+1], be careful with OutOfBoundException. Return when preL == preR. This makes sure after that, preL will not be out of index bound.

Time Complexity: O(n).

Space: O(n).

AC Java:  

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        if(pre == null || pre.length == 0 || post == null || post.length == 0){
            return null;
        }
        
        HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
        for(int i = 0; i<post.length; i++){
            hm.put(post[i], i);
        }
        
        return construct(pre, 0, pre.length-1, post, 0, post.length-1, hm);
    }
    
    private TreeNode construct(int[] pre, int preL, int preR, int[] post, int postL, int postR, HashMap<Integer, Integer> hm){
        if(preL > preR){
            return null;
        }
        
        TreeNode root = new TreeNode(pre[preL]);
        if(preL == preR){
            return root;
        }
        
        int leftVal = pre[preL+1];
        int leftIndex = hm.get(leftVal);
        root.left = construct(pre, preL+1, preL+1+leftIndex-postL, post, postL, leftIndex, hm);
        root.right = construct(pre, preL+2+leftIndex-postL, preR, post, leftIndex+1, postR-1, hm);
        return root;
    }
}

类似Construct Binary Tree from Preorder and Inorder Traversal, Construct Binary Tree from Inorder and Postorder Traversal.