欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数算 由中根序列和后根序列重建二叉树 二叉树

程序员文章站 2024-03-19 22:02:10
...

题目内容:
我们知道如何按照三种深度优先次序来周游一棵二叉树,来得到中根序列、前根序列和后根序列。反过来,如果给定二叉树的中根序列和后根序列,或者给定中根序列和前根序列,可以重建一二叉树。本题输入一棵二叉树的中根序列和后根序列,要求在内存中重建二叉树,最后输出这棵二叉树的前根序列。
用不同的整数来唯一标识二叉树的每一个结点。

输入格式:
两行。第一行是二叉树的中根序列,第二行是后根序列。每个数字表示的结点之间用空格隔开。结点数字范围0~65535。暂不必考虑不合理的输入数据。

输出格式:
一行。由输入中的中根序列和后根序列重建的二叉树的前根序列。每个数字表示的结点之间用空格隔开。

输入样例:
9 5 32 67
9 32 67 5

输出样例:
5 9 67 32

感觉算法是错的,但是只有一个样例,还是AC了

#include <iostream>
using namespace std;

struct tree
{
	tree* left;
	tree* right;
	int val;
	int flag;
};
int a[65536];
int b[65536];
int n;
void buildrighttree(tree*, int, int, int, int, int);
void buildlefttree(tree* root, int le, int ri, int rootnum, int lenl, int lenr)
{
	root->left = new tree;
	if (le > ri)
	{
		root->left->val = -1;
		return;
	}
	root->left->val = b[rootnum - lenr - 1];
	if (le == ri)
	{
		root->left->left = new tree;
		root->left->right = new tree;
		root->left->left->val = -1;
		root->left->right->val = -1;
		return;
	}
	int k;
	for (int i = 0; i < lenl; i++)
	{
		if (a[i + le] == root->left->val)
		{
			k = i;
			break;
		}
	}
	buildlefttree(root->left, le, le + k - 1, rootnum - lenr - 1, k, lenl - k - 1);
	buildrighttree(root->left, le + k + 1, ri, rootnum - lenr - 1, k, lenl - k - 1);
}
void buildrighttree(tree* root, int le, int ri, int rootnum, int lenl, int lenr)
{
	root->right = new tree;
	if (le > ri)
	{
		root->right->val = -1;
		return;
	}
	root->right->val = b[rootnum - 1];
	if (le == ri)
	{
		root->right->left = new tree;
		root->right->right = new tree;
		root->right->left->val = -1;
		root->right->right->val = -1;
		return;
	}
	int k;
	for (int i = 0; i < lenr; i++)
	{
		if (a[i + le == root->right->val])
		{
			k = i;
			break;
		}
	}
	buildlefttree(root->right, le, le + k - 1, rootnum - 1, k, lenr - k - 1);
	buildrighttree(root->right, le + k + 1, ri, rootnum - 1, k, lenr - k - 1);
}
void dfs(tree* root)
{
	cout << " " << root->val;
	if (root->left->val != -1)
		dfs(root->left);
	if (root->right->val != -1)
		dfs(root->right);
}
int main()
{
	char c;
	c = getchar();
	n = 0;
	while (c != '\n')
	{
		if (c != ' ')
		{
			ungetc(c, stdin);
			cin >> a[n];
			n++;
		}
		c = getchar();
	}
	for (int i = 0; i < n; i++)
	{
		cin >> b[i];
	}
	int leftl;
	int leftr;
	int rightl;
	int rightr;
	tree* root = new tree;
	root->val = b[n - 1];
	for (int i = 0; i < n; i++)
	{
		if (a[i] == root->val)
		{
			leftl = 0;
			leftr = i - 1;
			rightl = i + 1;
			rightr = n - 1;
			break;
		}
	}
	buildlefttree(root, leftl, leftr, n - 1, leftr - leftl + 1, rightr - rightl + 1);
	buildrighttree(root, rightl, rightr, n - 1, leftr - leftl + 1, rightr - rightl + 1);
	cout << root->val;
	if (root->left->val != -1)
		dfs(root->left);
	if (root->right->val != -1)
		dfs(root->right);

    return 0;
}


相关标签: 数算