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:

TreeNode *buildTreeUtil(vector<int> &inorder, int iLeft, int iRight, vector<int> &postorder, int pLeft, int pRight) {
    if (iLeft > iRight || pLeft > pRight) return NULL;

    TreeNode *node = new TreeNode(postorder[pRight]);

    int i;
    for (i=iLeft; i<=iRight; i++) {
        if (node->val == inorder[i]) break;
    }

    node->left = buildTreeUtil(inorder, iLeft, i - 1, postorder, pLeft, pLeft + i - iLeft - 1);
    node->right = buildTreeUtil(inorder, i + 1, iRight, postorder, pLeft + i - iLeft, pRight - 1);
    return node;
}

TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
    return buildTreeUtil(inorder, 0, (int)inorder.size()-1, postorder, 0, (int)postorder.size()-1);
}