1 #include <iostream> 2 #include <vector> 3 #include <algorithm> 4 #include <queue> 5 #include <stack> 6 #include <string> 7 #include <fstream> 8 #include <map> 9 using namespace std; 10 11 struct node { 12 int data; 13 struct node *left, *right; 14 node() : data(0), left(NULL), right(NULL) { } 15 node(int d) : data(d), left(NULL), right(NULL) { } 16 }; 17 18 void prints(node *root) { 19 if (!root) return; 20 prints(root->left); 21 cout << root->data << " "; 22 prints(root->right); 23 } 24 25 node *_buildtree(int pre[], int post[], int &preindex, int l, int h, int size) { 26 if (preindex >= size || l > h) return NULL; 27 node *root = new node(pre[preindex++]); 28 if (l == h) return root; 29 int i = l; 30 for (; i <= h; i++) if (pre[preindex] == post[i]) break; 31 if (i <= h) { 32 root->left = _buildtree(pre, post, preindex, l, i, size); 33 root->right = _buildtree(pre, post, preindex, i+1, h, size); 34 } 35 return root; 36 } 37 38 node *buildtree(int pre[], int post[], int size) { 39 int preindex = 0; 40 return _buildtree(pre, post, preindex, 0, size-1, size); 41 } 42 43 int main() { 44 int pre[9] = {1, 2, 4, 8, 9, 5, 3, 6, 7}; 45 int post[9] = {8, 9, 4, 5, 2, 6, 7, 3, 1}; 46 node *root = buildtree(pre, post, 9); 47 prints(root); 48 return 0; 49 }