7-28 搜索树判断 (25 分)

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct TNode *tree;
struct TNode
{
    int data;
    tree lchild;
    tree rchild;
};
int flag = 0;   //控制最后一个输出后面没有空格
int flag1 ;     //如果不是二叉搜索树返回1
int flag2 ;     //如果不是二叉镜像搜索树返回1

void Print( tree t);
tree Find ( int pre[],int len);
tree FindMirror( int pre[],int len);

int main()
{
    int len;
    int pre[1005];
    int i;
    tree t,tm;

    scanf("%d",&len);
    for( i=0; i<len; i++)
    {
        scanf("%d",&pre[i]);
    }

    t = Find( pre,len);
    tm = FindMirror( pre,len );
    if( t && !flag1)
    {
        //树不为空并且是二叉搜索树
        printf("YES\n");
        Print( t );
        printf("\n");
    }
    else if( tm && !flag2)
    {
        //树不为空并且是二叉镜像搜索树
        printf("YES\n");
        Print( tm );
        printf("\n");
    }
    else printf("NO\n");

    return 0;
}


tree Find ( int pre[],int len)
{
    int i,j;

    if( !len ) return NULL;
    tree temp = (tree) malloc( sizeof( struct TNode));
    temp->data = *pre;

    for( i=1; i<len; i++)
    {
        if( pre[i] >= temp->data)
            //寻找右子树
            break;
    }
    for( j=i; j<len; j++)
    {
        if( pre[j] < temp->data)
        {
            //右子树中有小于根结点的值，不是二叉搜索树
            flag1 = 1;
            return NULL;
        }
    }
    temp->lchild = Find( pre+1, i-1);
    temp->rchild = Find( pre+i, len-i);
    return temp;
}
tree FindMirror( int pre[],int len)
{
    //镜像树，左子树大于根大于右子树
    int i,j;

    if( !len ) return NULL;
    tree temp = (tree) malloc( sizeof( struct TNode));
    temp->data = *pre;

    for( i=1; i<len; i++)
    {
        if( pre[i] < temp->data)
            //寻找右子树
            break;
    }
    for( j=i; j<len; j++)
    {
        if( pre[j] >= temp->data)
        {
            //右子树中有大于等于根结点的值，不是二叉搜索树
            flag2 = 1;
            return NULL;
        }
    }
    temp->lchild = FindMirror( pre+1, i-1);
    temp->rchild = FindMirror( pre+i, len-i);
    return temp;
}

void Print( tree t)
{

    if( t )
    {
        //后序遍历
        Print(t->lchild);
        Print(t->rchild);
        if( !flag ) flag = 1;
        else printf(" ");
        printf("%d",t->data);
    }
}