1 #include 
     
       2  3 using namespace std; 4  5 struct Node 6 { 7     Node(int v):value(v),left(NULL), right(NULL){} 8     struct Node * left; 9     struct Node * right;10     int value;11 };12 int length;13 Node *  BuildTree(int * preorder, int * inorder, int  * pos, int start, int end)14 {15     if((*pos) >= length) return NULL;16     //if(start >= end)  return NULL;17     Node * root = new Node(preorder[*pos]);18     int i;19     for(i = start; i < end; ++i)20         if(inorder[i] == preorder[*pos])21             break;22     //if(i == end) return NULL;23     24     if(i > start)25     {26         *pos = *pos + 1;27         root->left  = BuildTree(preorder, inorder, pos, start, i);28     }29     if(end > i+1)30     {31         *pos = *pos + 1;32         root->right = BuildTree(preorder, inorder, pos, i+1, end);33     }34     return root;35     36 }37 void InorderOutput(Node * root)38 {39     if(NULL == root) return;40     InorderOutput(root->left);41     cout << root->value << " ";42     InorderOutput(root->right);43 }44 void FreeTree(Node * root)45 {46     if(NULL == root) return;47     FreeTree(root->left);48     FreeTree(root->right);49     delete root;50 }51 int main()52 {53     int n;54     while(cin >> n)55     {56         length = n;57         int * preorder = new int[n];58         int * inorder  = new int[n];59         for(int i = 0; i < n; ++i)60             cin >> preorder[i];61         for(int j = 0; j < n; ++j)62             cin >> inorder[j];63         int k = 0;64         Node * root = BuildTree(preorder, inorder, &k, 0, n);65         InorderOutput(root);66         cout << endl;67 //         if(isTree)68 //             cout << "Yes" << endl;69 //         else cout << "NO" << endl;70         delete preorder;71         delete inorder;72         FreeTree(root);73     }74     return 0;75 }