Construct Binary Tree from Preorder and Inorder Traversal

题目：

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

分析：

这道题目的解题步骤是：

(1) 从preorder的第一个元素取出root的值，
(2) 拿这个值去inorder找到root的位置，
(3) inorder中root左边是left sub tree, 右边是right sub tree,
(4) left sub tree中有(rootPos-istart)个元素
(5) preorder的第2个元素是left sub tree起点，2+(rootPos-istart)是中点
(6) 从rootPos+1开始右边部分是right sub tree

如果用图解的方法，我有一棵树是

preorder
1, 2, 3, 4, 5
|
pstart

inorder
4, 2, 5, 1, 3
|        |
istart   rootPos

解法：

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

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

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

        return root;
    }

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