hdu 1710 Binary Tree Traversals (二叉树）

 1 /**********************************************************
 2 题目：   Binary Tree Traversals（hdu 1710）
 3 链接：   http://acm.hdu.edu.cn/showproblem.php?pid=1710
 4 题意：   给出二叉树的先序和中序遍历结果，求后序遍历结果
 5 算法：   二叉树
 6 思路：   先以先序和中序建树，先序的第一个点是根节点，中序
 7          和先序第一个点相同的位置前所有点都是左子树，所以
 8          就可以递归来建树，最后给树后序遍历就可以了。
 9 ***********************************************************/
10 #include<cstdio>
11 #include<cstring>
12 #include<algorithm>
13 #include<iostream>
14 #include<cstdlib>
15 using namespace std;
16 
17 const int mx=1004;
18 typedef struct Tree
19 {
20     Tree *left,*right;
21     int num;
22 }Tree;
23 Tree *tree;
24 
25 Tree *getree(int *a,int *b,int n)
26 {
27     Tree *s;
28 
29     for (int i=0;i<n;i++)
30     {
31         if (b[i]==a[0])
32         {
33             s=(Tree *)malloc(sizeof(Tree));
34             s->num=a[0];
35             s->left=getree(a+1,b,i);
36             s->right=getree(a+i+1,b+i+1,n-i-1);
37             return s;
38         }
39     }
40     return NULL;
41 }
42 
43 void Find(Tree *p)
44 {
45     if (p==NULL) return ;
46     Find(p->left);
47     Find(p->right);
48     if (p==tree) printf("%d
",p->num);
49     else printf("%d ",p->num);
50     delete(p);
51 }
52 
53 int main()
54 {
55     int a[mx],b[mx];
56     int n;
57     while (~scanf("%d",&n))
58     {
59         for (int i=0;i<n;i++) scanf("%d",&a[i]);
60         for (int i=0;i<n;i++) scanf("%d",&b[i]);
61         tree=getree(a,b,n);
62         Find(tree);
63     }
64 }

 1 /********************************************************
 2 这题也可边建树边输出
 3 *********************************************************/
 4 #include<iostream>
 5 #include<cstdio>
 6 #include<cstring>
 7 #include<cstdlib>
 8 using namespace std;
 9 
10 const int mx=1004;
11 
12 void dfs(int *a,int *b,int n,int flag)
13 {
14     for (int i=0;i<n;i++)
15     {
16         if (a[0]==b[i])
17         {
18             dfs(a+1,b,i,0);
19             dfs(a+i+1,b+i+1,n-i-1,0);
20             if (flag) printf("%d
",a[0]);
21             else printf("%d ",a[0]);
22         }
23     }
24 }
25 
26 int main()
27 {
28       int a[mx],b[mx];
29       int n;
30       while (~scanf("%d",&n))
31       {
32           for (int i=0;i<n;i++) scanf("%d",&a[i]);
33           for (int i=0;i<n;i++) scanf("%d",&b[i]);
34           dfs(a,b,n,1);
35       }
36 }