二叉树遍历（已知中序、先序求后序）-蒲公英云

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

灰太狼 2022-06-09 10:38 333阅读 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

Submit Status Statistics Discuss

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

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

Submit Status Statistics Discuss

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;
}