算法
1.根据题意,需要先判断该序列是否是二叉搜索树或者其镜像的前序遍历。
2.对于二叉搜索树而言:设根节点为l
,序列末尾为r
,易知在序列中一定存在下标为i和j
的点,使得l+1 ~ i
的下标对应元素均小于pre[l]
,而j ~ r
的下标对应元素均大于等于pre[l]
,故可以令i = l+1, j = r
,遍历前序遍历,若i - j == 1
则说明这是二叉搜索树,反之则说明不是。同时,在判断是否是前序遍历的同时,可以记录后序遍历的信息,l+1 ~ j
是新的左半边区间,i ~ r
是新的右半边区间,最后将pre[l]
存储即可。当存储后的元素个数等于n
时说明是二叉搜索树,否则再判断是否是镜像。
3.对于镜像而言:方法同上,如果个数也不等于n
则输出NO
。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int n;
int pre[N];
bool isMirror;
vector<int> ans;
void dfs(int l,int r)
{
if(l>r) return ;
int i = l + 1,j = r;
if(!isMirror)
{
while(i<=r&&pre[i]<pre[l]) i++;
while(j>=l+1&&pre[j]>=pre[l]) j--;
}
else
{
while(i<=r&&pre[i]>=pre[l]) i++;
while(j>=l+1&&pre[j]<pre[l]) j--;
}
if(i-j!=1) return;
dfs(l+1,j);
dfs(i,r);
ans.push_back(pre[l]);
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>pre[i];
dfs(1,n);
if(ans.size()==n)
{
cout<<"Yes"<<endl;
for(int i=0;i<n;i++)
if(i==0) cout<<ans[i];
else cout<<" "<<ans[i];
}
else
{
isMirror = true;
ans.clear();
dfs(1,n);
if(ans.size()==n)
{
cout<<"Yes"<<endl;
for(int i=0;i<n;i++)
if(i==0) cout<<ans[i];
else cout<<" "<<ans[i];
}
else cout<<"No";
}
}