1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | /** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) { if(pre.empty()) return NULL; if(pre.size()==1) return new TreeNode(pre[0]); TreeNode *root=new TreeNode(pre[0]); vector<int>::iterator ite1=in.begin(); vector<int>::iterator ite2=in.end(); int leftNum=0; int rightNum=0; for(;ite1!=ite2;ite1++) { if(*ite1!=root->val)leftNum++; else break; } rightNum=pre.size()-1-leftNum; vector<int>lson_pre(leftNum,0); lson_pre.assign(pre.begin()+1,pre.begin()+1+leftNum); vector<int>lson_in(leftNum,0); lson_in.assign(in.begin(),in.begin()+leftNum); vector<int>rson_pre(rightNum,0); rson_pre.assign(pre.end()-rightNum,pre.end()); vector<int>rson_in(rightNum,0); rson_in.assign(in.end()-rightNum,in.end()); root->left=reConstructBinaryTree(lson_pre,lson_in); root->right=reConstructBinaryTree(rson_pre,rson_in); return root; }}; |
原文：http://www.cnblogs.com/zhxshseu/p/5285172.html