Construct Binary Tree from Preorder and Inorder Traversal

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

Have you met this question in a real interview? 

Yes

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.

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) {

        // write your code here

        return building(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);

    }

    

    private TreeNode building(int[] preorder, int preStart, int preEnd, int[] inorder, int iS, int iE){

        if(iS > iE || preStart > preEnd){

            return null;

        }

        TreeNode root = new TreeNode(preorder[preStart]);

        int idx = 0;

        for(int i = iS; i <= iE; i++){

            if(inorder[i] == preorder[preStart]){

                idx = i;

                break;

            }

        }

        root.left = building(preorder, preStart+1, preStart+(idx-iS), inorder, iS, idx-1);

        root.right = building(preorder, preStart+(idx-iS)+1, preEnd, inorder, idx+1, iE);

        return root;

        

    }

}