16. Construct Binary Tree from Inorder and Postorder Traversal

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

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

For example, given

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

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

Solution: (Recursion)

class Solution
{
public:
    int find(vector<int> inorder, int node, int inStart, int inEnd)
    {

        for (int i = inStart; i <= inEnd; i++)
        {
            if (inorder[i] == node)
            {
                return i;
            }
        }
        return -1;
    }
    
    TreeNode *createTree(vector<int> inorder, vector<int> postorder, int inStart, int inEnd, int postStart, int postEnd)
    {

        if (inStart > inEnd)
        {
            return NULL;
        }

        TreeNode *t = new TreeNode;
        t->val = postorder[postEnd];

        int idx = find(inorder, postorder[postEnd], inStart, inEnd);

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

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

        t->left = createTree(inorder, postorder, lis, lie, lps, lpe);
        t->right = createTree(inorder, postorder, ris, rie, rps, rpe);
        return t;
    }

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

        int n = inorder.size();
        int m = inorder.size();
        TreeNode *t = createTree(inorder, postorder, 0, n - 1, 0, m - 1);
        return t;
    }
};