1、HDU 1710 Binary Tree Traversals
2、链接：http://acm.hust.edu.cn/vjudge/problem/33792
3、总结：记录下根结点，再拆分左右子树，一直搜下去。感觉像dfs。
题意：二叉树，输入前、中序求后序。
(1)建立出一颗二叉树，更直观。但那些指针用法并不是很懂。
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std; typedef struct tree
{
tree *l,*r;
int num;
};
tree *root; tree *build(int *a,int *b,int n)
{
tree *s;
for(int i=;i<n;i++)
{
if(a[]==b[i]){
s=(tree *)malloc(sizeof(tree)); //不要漏了这个 s->num=b[i];
s->l=build(a+,b,i);
s->r=build(a+i+,b+i+,n-i-);
return s;
}
} return NULL;
} void postorder(tree *ro)
{
if(ro==NULL)return ;
postorder(ro->l);
postorder(ro->r);
if(ro==root){
printf("%d\n",ro->num);
}
else {
printf("%d ",ro->num);
}
} int main()
{
int n;
int a[],b[];
while(scanf("%d",&n)!=EOF)
{
for(int i=;i<n;i++)
scanf("%d",&a[i]);
for(int i=;i<n;i++)
scanf("%d",&b[i]); root=build(a,b,n);
postorder(root);
} return ;
}
(2)直接在遍历时输出。
#include<iostream>
#include<cstdio>
using namespace std; void preorder(int *a,int *b,int n,int flag)
{
for(int i=;i<n;i++)
{
if(a[]==b[i]){
preorder(a+,b,i,);
preorder(a+i+,b+i+,n-i-,);
if(flag){
printf("%d\n",a[]);
}
else {
printf("%d ",a[]);
}
}
}
return ;
} int main()
{
int n,a[],b[];
while(scanf("%d",&n)!=EOF)
{
for(int i=;i<n;i++)
scanf("%d",&a[i]);
for(int i=;i<n;i++)
scanf("%d",&b[i]); preorder(a,b,n,);
} return ;
}