Construct Binary Tree from Preorder and Inorder Traversal

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

Notice

You may assume that duplicates do not exist in the tree.

Example

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

  2
 / \
1   3

Solution: Use the preorder property and divide conquer build tree.

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if(preorder.length != inorder.length) {
        return null;
    }
    return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}

public TreeNode buildTree(int[] preorder, int pstart, int pend, int[] inorder, int istart, int iend) {
    if(pstart > pend || istart > iend) {
        return null;
    }
    TreeNode root = new TreeNode(preorder[pstart]);
    int proot = 0;
    for(int i = 0; i < inorder.length; i++) {
        if(inorder[i] == root.val) {
            proot = i;
            break;
        }
    }
    int len = proot - istart;
    root.left = buildTree(preorder, pstart + 1, pstart + len, inorder, istart, proot - 1);
    root.right = buildTree(preorder, pstart + len + 1, pend, inorder, proot + 1, iend);
    return root;
}