šŸŒŸConstruct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
 * Build a hashmap. Key: values of elements; Value: element index
 * The last element of postorder is the root
 * Find the index of root in inorder by using the hashmap. 
 * split inorder array. 
 * split postorder array. 
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private HashMap<Integer, Integer> map = new HashMap<Integer, Integer> ();  
    public TreeNode buildTree(int[] inorder, int[] postorder) {  
        if (inorder == null || postorder == null || inorder.length == 0 || postorder.length == 0) {
            return null; 
        }
        //Create a hashmap for the value index of inorder array 
        //So that in the helper function, we can find the index of a value. 
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        
        return helper( postorder, 0, inorder.length-1, 0, postorder.length-1); 
    }
    
    private TreeNode helper (int[] postorder, int inL, int inR, int postL, int postR) {
        if (inL > inR || postL > postR) 
            return null; 
        TreeNode root = new TreeNode(postorder[postR]); 
        //get the index of the root
        int index = map.get(root.val);
        //split the inorder array based on the root index 
        root.left = helper (postorder, inL, index-1, postL, postL+index-inL-1);
        //split the postorder array based on the root index and inR
        root.right = helper (postorder, index+1, inR, postR-(inR-index), postR-1);
        
        return root; 
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s