poj2255 Tree Recovery

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 using namespace std;
 5 struct Node
 6 {
 7     char data;
 8     Node *lchild;
 9     Node *rchild;
10 };
11 Node *CreatTree(string pre,string in)
12 {
13     Node *root=NULL;
14     if(pre.length()>0)
15     {
16         root=new Node;
17         root->data=pre[0];
18         int index=in.find(root->data);
19         root->lchild=CreatTree(pre.substr(1,index),in.substr(0,index));
20         root->rchild=CreatTree(pre.substr(index+1),in.substr(index+1));
21     }
22     return root;
23 }
24 void Postorder(Node *root)
25 {
26     if(root!=NULL)
27     {
28         Postorder(root->lchild);
29         Postorder(root->rchild);
30         putchar(root->data);
31     }
32 }
33 int main()
34 {
35     Node *root;
36     string pre,in;
37     while(cin>>pre>>in)
38     {
39         root=CreatTree(pre,in);
40         Postorder(root);
41         putchar('\n');
42     }
43     return 0;
44 }

先递归根据前序和中序进行建树，后递归进行后序遍历就行了！这和nyoj221一样！！刚开始在poj老是cp，结果是因为选错了语言！！