Leetcode-889 Construct Binary Tree from Preorder and Postorder Traversalf(根据前序和后序遍历构造二叉树)

 1 class Solution
 2 {
 3     public:
 4         TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post)
 5         {
 6             if(pre.size()==0)
 7                 return NULL;
 8             TreeNode *node = new TreeNode(pre[0]);
 9             if(pre.size()==1)
10                 return node;
11             int i;
12             for(i = 0;pre[1]!=post[i];i ++)
13                 ;
14             int len = i+1;
15         //    cout << len << endl;
16             vector<int> tmp_pre1;
17             tmp_pre1.insert(tmp_pre1.begin(),pre.begin()+1,pre.begin()+len+1);
18             vector<int> tmp_post1;
19             tmp_post1.insert(tmp_post1.begin(),post.begin(),post.begin()+len);
20             vector<int> tmp_pre2;
21             tmp_pre2.insert(tmp_pre2.begin(),pre.begin()+len+1,pre.end());
22             vector<int> tmp_post2;
23             tmp_post2.insert(tmp_post2.begin(),post.begin()+len,post.end());
24             node->left = constructFromPrePost(tmp_pre1, tmp_post1);
25             node->right = constructFromPrePost(tmp_pre2, tmp_post2);
26             return node;
27         }
28 };