Leetcode: Construct Binary Tree from Preorder and Inorder Traversal

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

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

Solution:

We implement the algorithm recursively, for instance given the tree to obtain


That corresponds to the lists:
preorder: A B D E C and inorder: D B E A C

We see that the first element of the preorder corresponds to the root value, A.
Note that by definition:

• All the elements in the inorder tree previous to this element (A) belong to the left tree and appear in the preorder tree just after the root.
• All the elements in the inorder tree after this element (A) belong to the right tree and appear in the preorder tree at the end.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree(preorder, inorder, 0, 0, preorder.length);
    }
    
    public TreeNode buildTree(int[] preorder, int[] inorder, 
        int indexPreOrder, int indexInOrder, int elements)
    {
        if(elements==0)
            return null;
        TreeNode solution = new TreeNode(preorder[indexPreOrder]);
        if(elements==1)
            return solution;
        int elementLeftTree=0;
        for(int i=indexInOrder; inorder[i] != preorder[indexPreOrder];
            i++, elementLeftTree++);
        solution.left = buildTree(preorder, inorder, indexPreOrder+1, 
            indexInOrder, elementLeftTree);
        solution.right = buildTree(preorder, inorder, indexPreOrder+elementLeftTree+1, 
            indexInOrder+elementLeftTree+1, elements-1-elementLeftTree);
        return solution;
    }
}