重建二叉树

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 
11  #include <vector>
12  #include <iostream>
13 
14  using namespace std;
15 
16 class Solution {
17 public:
18     TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
19 
20     }
21 };
22 
23 
24 TreeNode * Solution::reConstructBinaryTree(vector<int> pre, vector<int> vin)
25 {
26     int vin_size = vin.size();
27     if(vin_size == 0)  //递归终止条件
28         return NULL;29     int temp;
30 
31     for(int i = 0; i < vin_size; i++)
32     {
33         if(pre[0] == vin[i])
34         {
35             temp = i;
36             break;
37         }
38     }
39 
40     TreeNode* node = new TreeNode(vin[temp]);
41 
42     vector<int> lvin, rvin, lpre, rpre;
43 
44     for(int j = 0; j < temp; j++)
45         lrin.push_back(vin[j]);
46     for(int t = temp+1; t < vin_size; t++)
47         rvin.push_back(vin[t]);
48 
49     for(int x = 1; x < temp+1; x++)
50         lpre.push_back(pre[x]);
51     for(int y = temp+1；y < vin_size; y++)
52         rpre.push_back(pre[y]);
53 
54 
55     node->left  = reConstructBinaryTree(lpre, lvin);//递归左子树
56     node->right = reConstructBinaryTree(rpre, rvin);//递归重建右子树
57 
58 
59     return node;
60 }