LeetCode OJ--Construct Binary Tree from Preorder and Inorder Traversal *

http://oj.leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

根据二叉树的前序遍历和中序遍历序列求二叉树

学习：迭代器的使用和auto变量

#include <iostream>
#include <vector>
using namespace std;

 struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };

 
class Solution{
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) 
    {
        return buildTree(begin(preorder),end(preorder),begin(inorder),end(inorder));
    }

    template<typename InputIterator>
    TreeNode* buildTree(InputIterator pre_first,InputIterator pre_last,InputIterator in_first,InputIterator in_last)
    {
        if(pre_first == pre_last)
            return nullptr;
        if(in_first ==in_last)
            return nullptr;

        auto root = new TreeNode(*pre_first);

        auto inRootPos = find(in_first,in_last,*pre_first);
        auto leftSize = distance(in_first,inRootPos);

        root->left = buildTree(next(pre_first),next(pre_first,leftSize+1),in_first,next(in_first,leftSize));
        root->right = buildTree(next(pre_first,leftSize+1),pre_last,next(inRootPos),in_last);

        return root;
    }
};

int main()
{
    Solution myS;
    int arr1[7] = {1,2,4,5,3,6,7 };
    int arr2[7] = {4,2,5,1,6,3,7 };
    vector<int> inorder(arr1,arr1+7) ;
    vector<int> postorder(arr2 ,arr2+7);
    TreeNode *myNode;

    myNode = myS.buildTree(inorder,postorder);
     
    cout<<"hi"<<endl;
    return 0;
}