Construct Binary Tree from Inorder and Postorder Traversal

题目：

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

分析：

道理和用preorder + inorder是一样的，但是有个细节肯定会错，这时候从postorder里面取值的时候取*(pend - 1)而不是*pend。

因为iterator长得是这样的:
 1, 2, 3, 4, 5
|           | |
pstart      | pend
            pend - 1

可能他只是想用pend作为终止循环的一个要求吧~

解法：

class Solution {
    /**
     *@param inorder : A list of integers that inorder traversal of a tree
     *@param postorder : A list of integers that postorder traversal of a tree
     *@return : Root of a tree
     */
public:
    typedef vector<int>::iterator Iter;
    TreeNode* dfs(Iter istart, Iter iend, Iter pstart, Iter pend) {
        if (istart == iend) {
            return NULL;
        }

        int rootValue = *(pend - 1);
        Iter rootPos = find(istart, iend, rootValue);
        TreeNode* root = new TreeNode(rootValue);

        root->left = dfs(istart, istart + (rootPos - istart), pstart, pstart + (rootPos - istart) );
        root->right = dfs(rootPos + 1, iend, pstart + (rootPos - istart), pend - 1);
        return root;
    }

    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        // write your code here
        if (inorder.size() != postorder.size() ) {
            return NULL;
        }
        return dfs(inorder.begin(), inorder.end(), postorder.begin(), postorder.end() );
    }
};