Construct Binary Tree from Preorder and Inorder Traversal

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

Note:
 * Build a hashmap. Key: values of elements; Value: element index
 * The first element of preorder is the root
 * Find the index of root in inorder by using the hashmap.
 * split inorder array.
 * split preorder array.
public class Solution {
    private HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null 
         || preorder.length == 0 || inorder.length == 0) {
             return null; 
         }
         for (int i = 0; i < inorder.length; i++) {
             map.put (inorder[i], i);
         }
         
         return helper (preorder, 0, inorder.length - 1, 0, preorder.length - 1);
    }
    
    private TreeNode helper (int[] preorder, int inL, int inR, int preL, int preR) {
        if (inL > inR || preL > preR) {
            return null; 
        }
        TreeNode root = new TreeNode (preorder[preL]);
        int index = map.get(root.val); 
        root.left = helper (preorder, inL, index-1, preL+1, index-inL+preL);
        root.right = helper (preorder, index+1, inR, preL+index-inL+1, preR);
        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