注意点
- BST排序之后就是中序遍历
- 镜像情况下倒序遍历:涉及到相等值在左边还是右边的问题
- cnt全局变量记得清零
代码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 1010;
int preorder[N], inorder[N], postorder[N];
int n, cnt;
bool build(int il, int ir, int pl, int pr, int type)
{
if (il > ir) return true;
int root = preorder[pl];
int k;
if (type == 0)
{
for (k = il; k <= ir; k++)
{
if (inorder[k] == root)
break;
}
if (k > ir) return false;
}
else
{
for (k = ir; k >= il; k--) //涉及想等值在哪边的问题
{
if (inorder[k] == root)
break;
}
if (k < il) return false;
}
bool ans = true;
if (!build(il, k - 1, pl + 1, pl + 1 + (k - 1 - il), type)) ans = false;
if (!build(k + 1, ir, pl + 1 + (k - 1 - il) + 1, pr, type)) ans = false;
postorder[cnt++] = root;
return ans;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> preorder[i];
inorder[i] = preorder[i];
}
sort(inorder, inorder + n);
if (build(0, n - 1, 0, n - 1, 0))
{
cout << "YES" << endl;
for (int i = 0; i < n; i++)
{
cout << postorder[i];
if (i != n - 1) cout << ' ';
}
}
else
{
reverse(inorder, inorder + n);
cnt = 0;
if (build(0, n - 1, 0, n - 1, 1))
{
cout << "YES" << endl;
for (int i = 0; i < n; i++)
{
cout << postorder[i];
if (i != n - 1) cout << ' ';
}
}
else
{
cout << "NO";
}
}
return 0;
}