题目描述

一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，

其左子树中所有结点的键值小于该结点的键值；
其右子树中所有结点的键值大于等于该结点的键值；
其左右子树都是二叉搜索树。
所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。

给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。

输入格式：

输入的第一行给出正整数 N（≤1000）。随后一行给出 N 个整数键值，其间以空格分隔。

输出格式：

如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果，则首先在一行中输出 YES ，然后在下一行输出该树后序遍历的结果。数字间有 1 个空格，一行的首尾不得有多余空格。若答案是否，则输出 NO。

样例

输入样例1

7
8 6 5 7 10 8 11

输出样例1

YES
5 7 6 8 11 10 8

输入样例2

7
8 10 11 8 6 7 5

输出样例2

YES
11 8 10 7 5 6 8

输入样例3

7
8 6 8 5 10 9 11

输出样例3

NO

算法

递归建树(考察基础：树的递归)

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x):val(x),left(NULL),right(NULL){}
};
TreeNode* root;
int n,a[N];
int pre[N],cnt1;
int in[N],cnt2;

//对插入的总结：每次从根节点开始，每次不断地递归就行了
TreeNode* insert(TreeNode* root,int val)
{
    if(!root)root=new TreeNode(val);
    else if(root->val>val)root->left=insert(root->left,val);
    else root->right=insert(root->right,val);
    return root;
}

//前序遍历
void preorder(TreeNode* root)
{
    if(!root)return;
    pre[cnt1++]=root->val;
    preorder(root->left);
    preorder(root->right);
}

//后续遍历
void inorder(TreeNode* root)
{
    if(!root)return;
    inorder(root->left);
    inorder(root->right);
    in[cnt2++]=root->val;
}
//镜像
void mirror(TreeNode* root)
{
    if(!root)return;
    mirror(root->left);
    mirror(root->right);
    swap(root->left,root->right);
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        root=insert(root,a[i]);
    }
    bool flag=true;
    preorder(root);
    for(int i=0;i<n;i++)
        if(a[i]!=pre[i])
        {
            flag=false;
            break;
        }
    if(!flag)
    {
        flag=true;
        cnt1=0;
        mirror(root);
        preorder(root);
        for(int i=0;i<n;i++)
            if(a[i]!=pre[i]){flag=false;break;}
        if(flag)
        {
            inorder(root);
            cout<<"YES"<<endl;
            for(int i=0;i<cnt2;i++)
            {
                if(i) cout<<" ";
                cout<<in[i];
            }

        }
        else cout<<"NO"<<endl;
    }
    else
    {
        inorder(root);
        cout<<"YES"<<endl;
        for(int i=0;i<cnt2;i++)
        {
            if(i) cout<<" ";
            cout<<in[i];
        }

        return 0;
    }

}