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.

TreeNode* getnode(int x)

{

   TreeNode *t = (TreeNode *)malloc(sizeof(TreeNode));

    t->val = x;

    t->left =  NULL;

    t->right = NULL;

    return t;

}

TreeNode *buildTree(vector<int> &postorder, int pi, int pj, vector<int> &inorder, int ii, int ij)

{

    if(pi > pj)

      return NULL;

    TreeNode* root  = getnode(postorder[pj]);

    // find the index of number preorder[pi] in inorder

    int i = 0;

    for(i  = ii; i <= ij; i++)

    {

     if(postorder[pj] == inorder[i])

          break;

    }

    // count of elements in first half  

    int left  = (i - 1) - ii + 1;

    root->left = buildTree(postorder, pi , pi + left - 1, inorder, ii, ii + left -1);

    root->right = buildTree(postorder, pi+ left , pj -1, inorder, ii + left + 1, ij);

    return root;

}

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

    if(postorder.size() <= 0)

      return NULL;

    return buildTree(postorder, 0, postorder.size() - 1, inorder, 0, inorder.size() - 1);

}