1 #include <iostream> 2 #include <vector> 3 using namespace std; 4  5 struct TreeNode { 6      int val; 7      TreeNode *left; 8      TreeNode *right; 9      TreeNode(int x) : val(x), left(NULL), right(NULL) {}10  };11 12 class Solution {13 public:14     typedef vector<int>::iterator Iter;15     TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {16         return buildTreeRecur(inorder.begin(),inorder.end(),preorder.begin(),preorder.end());17     }18     TreeNode* buildTreeRecur(Iter istart,Iter iend,Iter pstart,Iter pend)19     {20         if (istart == iend) return NULL;21         int rootval = *pstart;22         Iter iterroot = find(istart,iend,rootval);23         TreeNode *res = new TreeNode(rootval);//建立根节点24         res->left = buildTreeRecur(istart,iterroot,pstart+1,pstart+1+(iterroot-istart));25         res->right = buildTreeRecur(iterroot+1,iend,pstart+1+(iterroot-istart),pend);//vector的end是最后元素还要再下一个！26         return res;27     }28 };29 30 void inorderTraversal(TreeNode* root)31 {32     if (root == nullptr) return;33     inorderTraversal(root->left);34     cout << root->val << " ";35     inorderTraversal(root->right);36 }37 void preorderTraversal(TreeNode* root)38 {39     if (root == nullptr) return;40     cout << root->val << " ";41     preorderTraversal(root->left);42     preorderTraversal(root->right);43 }44 int main()45 {46     Solution s;47     vector<int> inorder = {2,4,1,5,3};48     vector<int> preorder = { 1,2, 4,3, 5};49     TreeNode* root = s.buildTree(preorder,inorder);50     inorderTraversal(root);51     cout << endl;52     preorderTraversal(root);53     return 0;54 }