Construct Binary Tree from Preorder and Inorder Traversal

Source

• lintcode: Construct Binary Tree from Preorder and Inorder Traversal

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

Example
Given in-order [1,2,3] and pre-order [2,1,3], return a tree:

  2
 / \
1   3
Note
You may assume that duplicates do not exist in the tree.

Java

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */


public class Solution {
    /**
     *@param preorder : A list of integers that preorder traversal of a tree
     *@param inorder : A list of integers that inorder traversal of a tree
     *@return : Root of a tree
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i=0; i<inorder.length; i++){
            map.put(inorder[i], i);
        }
        return dfs(preorder, 0, map, 0, inorder.length-1);
    }

    public TreeNode dfs(int[] preorder, int cur, HashMap<Integer, Integer> inorder, int start, int end){
        if(start>end) return null;
        TreeNode root = new TreeNode(preorder[cur]);
        int mid = inorder.get(preorder[cur]);
        root.left=dfs(preorder, cur+1, inorder, start, mid-1);
        root.right=dfs(preorder, cur+mid-start+1, inorder, mid+1, end);
        return root;
    }
}