15. 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.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

Solution: (Recursion)

Using Point that in Preorder 1st element is the root

class Solution
{
public:
    int find(vector<int> inorder, int node, int start, int end)
    {

        for (int i = start; i <= end; i++)
        {
            if (inorder[i] == node)
            {
                return i;
            }
        }
        return -1;
    }

    TreeNode *createTree(vector<int> &preorder, vector<int> &inorder, int preStart, int preEnd, int inStart, int inEnd)
    {
        if (preStart > preEnd)
        {
            return NULL;
        }

        TreeNode *temp = new TreeNode;
        temp->val = preorder[preStart];

        int idx = find(inorder, preorder[preStart], inStart, inEnd);

        int lps = preStart + 1;
        int lis = inStart;
        int lie = idx - 1;
        int lpe = preStart + (lie - lis) + 1;

        int rps = lpe + 1;
        int rpe = preEnd;
        int ris = idx + 1;
        int rie = inEnd;

        temp->left = createTree(preorder, inorder, lps, lpe, lis, lie);
        temp->right = createTree(preorder, inorder, rps, rpe, ris, rie);

        return temp;
    }

    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)
    {

        int n = preorder.size();
        int m = inorder.size();

        TreeNode *t = createTree(preorder, inorder, 0, n - 1, 0, m - 1);
        return t;
    }
};