Luz4年前 (2021-03-08)题库1357

7-5 重建二叉树 (10 分)

给定一棵二叉树的前序遍历和中序遍历的结果，求其后序遍历。

输入格式:

输入可能有多组，以EOF结束。 每组输入包含两个字符串，分别为树的前序遍历和中序遍历。每个字符串中只包含字母和数字且互不重复。

输出格式:

对于每组输入，用一行来输出它后序遍历的结果。

输入样例:

ABDC BDAC
ABCD BADC

输出样例:

DBCA
BDCA

作者

李廷元

单位

民用航空飞行学院

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

#include<stdio.h>
#include<iostream>
#include<string.h>
#include <stdlib.h>
using namespace std;
char a[30], b[30];
struct Tree
{
	char val;
	Tree *left;
	Tree *right;
};
Tree *creatTree(Tree* p)
{
	p = (Tree*)malloc(sizeof(Tree));
	p->left = NULL;
	p->right = NULL;
	return p;
}
void bianli(Tree *p)
{
	if (p->left != NULL)
	{
		bianli(p->left);
	}
	if (p->right != NULL)
	{
		bianli(p->right);
	}
	cout <<p->val;
}
 
Tree *settree(int start1, int end1, int start2, int end2)
{
	Tree *root = NULL;
	root = creatTree(root);
	root->val = a[start1];
	int root1;
	for (int i = start2; i <= end2; i++)
	{
		if (b[i] == a[start1])
		{
			root1 = i;
			break;
		}
	}
	if (root1 != start2) 
	{
		root->left = settree(start1+1,start1+(root1-start2),start2,root1-1);
	}
	if (root1 != end2)
	{
		root->right = settree(start1+(root1-start2)+1,end1,root1+1,end2);
	}
	return root;
}
 
int main()
{
	Tree *root = NULL;
	while (scanf("%s%s", a,b) != EOF)
	{
		int len1 = strlen(a);
		int len2 = strlen(b);
 
		root = settree(0, len1 - 1, 0, len2 - 1);
		bianli(root);
		cout << endl;
	}
}