先序和中序构造二叉树_本题目要求用先序序列和中序序列构造一棵二叉树(树中结点个数不超过10个),并输出

本题目要求用先序序列和中序序列构造一棵二叉树（树中结点个数不超过10个），并输出其后序序列。

输入格式：

在第一行中输入元素个数。

第二行中输入先序序列，用空格分隔。

第三行中输入中序序列，用空格分隔。

输出格式：

输出此二叉树的后序序列，用空格分隔，最后也有一个空格。

输入样例：

5
10 20 30 40 50
20 10 40 30 50

输出样例：

20 40 50 30 10

代码展示：

#include <iostream>
using namespace std;

void getlast(int n,int *a,int *b);

int main() {
	int n;
	cin >> n;
	int prescan[40], midscan[40];
	int i;
	for (i = 0; i < n; i++) {
		cin >> prescan[i];
	}
	for (i = 0; i < n; i++) {
		cin >> midscan[i];
	}
	getlast(n,prescan,midscan);
	cout<<endl;
	system("pause");
	return 0;
}


void getlast(int n,int *a,int *b)
{
    if(n<=0){
        return ;
    }
    int root=a[0];
    int i;
    for(i=0;i<n;i++){
        if(b[i]==root){
            break;
        }
    }

    getlast(i,a+1,b);
    getlast(n-i-1,a+1+i,b+1+i);
    cout<<root<<" ";
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41