【题解】唯一二叉排序树

题意

给你一棵二叉排序树，由于一个序列构造出来的二叉排序树其也可能可以被其他的序列构造出来。所以判断该序列构造出的二叉排序树是否是唯一的是的话输出，否则输出

题解

首先，对于二叉排序树中的一个子树的根节点来说其左右儿子作为序列中的输入值，两者序列位置是不影响在二叉树的位置的，即交换序列中左右儿子的位置树中的位置不变。所以可以得到结论，当树当中有一个节点有两个儿子时其的构成序列就是不唯一的。所以我们判断输出的序列是否一根链即可。

复杂度

时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
struct BiTree
{
    int v;
    BiTree *lchild;
    BiTree *rchild;
};
int a[N];
void Insert(BiTree *&T,int v)
{
    if(T==NULL)
    {
        T=new BiTree;
        T->v=v;
        T->lchild=NULL;
        T->rchild=NULL;
        return;
    }
    if(T->v>v)
        Insert(T->lchild,v);
    else
        Insert(T->rchild,v);
}
bool flag=true;
void dfs(BiTree *T)
{
    if(T==NULL)
        return ;
    if(T->lchild!=NULL&&T->rchild!=NULL)
        flag=false;
    dfs(T->lchild);
    dfs(T->rchild);
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        BiTree *T=NULL;
        for(int i=0; i<n; i++)
        {
            scanf("%d",&a[i]);
            Insert(T,a[i]);
        }
        flag=true;
        dfs(T);
        if(flag)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}