数算 由中根序列和后根序列重建二叉树 二叉树
程序员文章站
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;
}