二叉树遍历（已知中序、先序求后序）

灰太狼 2022-06-09 10:38 167阅读 0赞

## 二叉树的遍历 ##

Time Limit: 1000ms

Memory Limit: 32768KB

This problem will be judged on **HRBUST**. Original ID: [2040][]  
64-bit integer IO format: **%lld** Java class name: **Main**

[Prev][]

[Submit][] [Status][] [Statistics][] [Discuss][]

[Next][]

给出一棵二叉树的中序和前序遍历，输出它的后序遍历。

### Input ###

本题有多组数据，输入处理到文件结束。

每组数据的第一行包括一个整数n，表示这棵二叉树一共有n个节点。

接下来的一行每行包括n个整数，表示这棵树的中序遍历。

接下来的一行每行包括n个整数，表示这棵树的前序遍历。

3<= n <= 100

### Output ###

每组输出包括一行，表示这棵树的后序遍历。

### Sample Input ###

7  
4 2 5 1 6 3 7

1 2 4 5 3 6 7

### Sample Output ###

4 5 2 6 7 3 1

### Source ###

[2014 Winter Holiday Contest 5][]

### Author ###

TwIStOy

[Prev][]

[Submit][] [Status][] [Statistics][] [Discuss][]

[Next][]

--------------------

Distributed under GPLv3. | [Project Homepage][] | Developer: [51isoft][] [crccw][] | Current Style: Cerulean.

#include<iostream>
    #include<cstring>
    using namespace std;
    int a1[110];
    int a2[110];
    int n;
     
    int findn(int a)
    {
    	for(int i=0;i<n;i++)
    	{
    		if(a2[i]==a) return i;
    	}
    	return -1;//要记得return-1 
    }
    void calc(int l1,int r1,int l2,int r2)//返回类型为void 
    {
    	 int m=findn(a1[l1]);
    	 if(m>l2) calc(l1+1,m-l2+1,l2,m-1);
    	 if(m<r2) calc(m-l2+l1+1,r1,m+1,r2);
    	 cout<<a1[l1]<<" ";
    }
    int main()
    {
    //	int n;
    	while(scanf("%d",&n)!=EOF)
    	{
    		memset(a1,0,sizeof(a1));
    		memset(a2,0,sizeof(a2));
    		for(int i=0;i<n;i++) cin>>a2[i];
    		for(int i=0;i<n;i++) cin>>a1[i];
    		calc(0,n-1,0,n-1);
    		cout<<endl;	
    	}
    	return 0;
    }

[2040]: http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=2040
[Prev]: http://www.bnuoj.com/v3/problem_show.php?pid=43466
[Submit]: http://www.bnuoj.com/v3/problem_show.php?pid=43467#
[Status]: http://www.bnuoj.com/v3/status.php?showpid=43467
[Statistics]: http://www.bnuoj.com/v3/problem_stat.php?pid=43467
[Discuss]: http://www.bnuoj.com/v3/discuss.php?pid=43467
[Next]: http://www.bnuoj.com/v3/problem_show.php?pid=43468
[2014 Winter Holiday Contest 5]: http://www.bnuoj.com/v3/problem.php#searchstr=2014+Winter+Holiday+Contest+5
[Project Homepage]: https://github.com/51isoft/bnuoj
[51isoft]: mailto:yichaonet
[crccw]: mailto:crccw@moonux.org