按照层次来构建树
#include <bits/stdc++.h>
using namespace std;
const int N = 50;
vector<int> level[N]; //存每一层的有效结点值
int post_num[N], in_num[N]; //存储后序、中序序列值
unordered_map<int, int> in; //{值, 下标},按值查找下标
//当前高度为h,当前后续序列区间[postL, postR],中序遍历区间[inL, inR]
void create(int h, int postL, int postR, int inL, int inR)
{
if (postL > postR)
{
return;
}
int root = post_num[postR]; //根节点的值
level[h].push_back(root);
int k = in[root]; //root在in里的下标
create(h + 1, postL, k + postL - inL - 1, inL, k - 1);
create(h + 1, k + postL - inL, postR - 1, k + 1, inR);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> post_num[i];
}
for (int i = 1; i <= n; i++)
{
cin >> in_num[i];
in.insert({in_num[i], i}); //在输入时存入键值对
}
create(1, 1, n, 1, n);
for (int i = 1; i <= n; i++)
{
for (auto x : level[i]) cout << x << ' ';
}
return 0;
}
不要用静态数组来存树
因为会有大量无效空间被浪费,而且当树退化成链表状时,需要的内存空间是指数级的,即使只有30个结点,也需要$2^{30} - 1$的数组大小。
例如:
30
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
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
静态数组只用来存完全二叉树。
而题目给出的序列构造出来的不一定是完全二叉树。
使用静态数组来存的WA代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
int tree[N];
int post_num[N], in_num[N];
unordered_map<int, int> post, in;
void create(int index, int postL, int postR, int inL, int inR)
{
if (postL > postR)
{
return;
}
tree[index] = post_num[postR]; //根节点的值
int k = in[tree[index]]; //root在in里的下标
if (!tree[index * 2]) create(index * 2, postL, k + postL - inL - 1, inL, k - 1);
if (!tree[index * 2 + 1]) create(index * 2 + 1, k + postL - inL, postR - 1, k + 1, inR);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> post_num[i];
post.insert({post_num[i], i});
}
for (int i = 1; i <= n; i++)
{
cin >> in_num[i];
in.insert({in_num[i], i});
}
create(1, 1, n, 1, n);
for (int i = 1; i <= N; i++)
if (tree[i]) cout << tree[i] << ' ';
return 0;
}