PAT 天梯赛练习集 L2-004. 这是二叉搜索树吗？-白红宇

PAT 天梯赛练习集 L2-004. 这是二叉搜索树吗？

阅读量：4993 次

发布时间：2019-06-12

本文共 1562 字，大约阅读时间需要 5 分钟。

题目链接:

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

其左子树中所有结点的键值小于该结点的键值；

其右子树中所有结点的键值大于等于该结点的键值；

其左右子树都是二叉搜索树。

所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。

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

输入格式：

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

输出格式：

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

输入样例1：

78 6 5 7 10 8 11

输出样例1：

YES5 7 6 8 11 10 8

输入样例2：

78 10 11 8 6 7 5

输出样例2：

YES11 8 10 7 5 6 8

输入样例3：

78 6 8 5 10 9 11

输出样例3：

NO 对于二叉搜索树中序遍历的结果唯一，因此将输入的数列从小到大、从大到小重排可以分别得到原树和镜像树的中序序列；已知前序和中序的数列可以确定一棵树，模拟建树，如果建成的树包含所有输入节点，则表示是二叉搜索树。因为数据范围1000，因此要模拟链表储存，我是用字符串'0'表示左孩子'1'表示右孩子然后对字符串建立索引作为存储下标。 代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #define INF 0x3f3f3f3f#define lowbit(x) (x&(-x))#define eps 0.00000001#define pn printf("\n")using namespace std;typedef long long ll;int pre[1005];int in[1005];int n, p, b;map 
                
                  mp;map 
                 
                   ind;int cnt = 0;void find(string S, int s, int e)// [s,e){ int k = -1; for(int i=s;i
                  
                   > n; for(int i=0;i
                   
                    > pre[i]; in[i] = pre[i]; } int fl = 0; { // zheng sort(in, in + n); p = 0; b = 0; find("", 0, n); if(mp.size() == n) { printf("YES\n"); fl = 1; print(""); pn; } } if(!fl) { // fan sort(in, in + n,[](int a, int b){ return a >= b;}); p = 0; b = 1; mp.clear(); find("", 0, n); if(mp.size() == n) { printf("YES\n"); fl = 1; print(""); pn; } } if(!fl) printf("NO\n");}

转载于:https://www.cnblogs.com/HazelNut/p/8506404.html

你可能感兴趣的文章