Java实现L2-004 这是二叉搜索树吗？ (25分)

阳光穿透心脏的1/2处 2023-02-24 08:36 110阅读 0赞

> “ 不要让将来的你，讨厌现在的自己”

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYWh1YW5f_size_16_color_FFFFFF_t_70_pic_center]

# 1.问题描述 #

**L2-004 这是二叉搜索树吗？ (25分)**

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

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

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

## 输入格式： ##

输入的第一行给出正整数 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

# 2.解题思路 #

按要求输入序列，假设其为二叉搜索树，遍历该树让左子树和右子树依次和根节点比较，如果满足条件遍历左子树的变量i和遍历右子树的变量j应该相差为1（二叉搜索树存在这样一个特点：根节点在最前面，然后后面跟了一段都比他小，再后面跟了一段都比他大）。如果两个变量相差不为1则不是二叉搜索树，但其可能是二叉搜索树的镜像。先假设其为二叉搜索树的镜像，再按照左子树比跟节点大右子树比根节点小的规则遍历集合，同样如果两个变量存在一次结果相差不为1（即存储后序遍历的集合不足N)，则其不是二叉搜索树的镜像。如果存储后序遍历的集合为N,则输出Yes，并输出该集合。

# 3.代码实现 #

import java.util.Scanner;
    import java.util.Vector;//初始化为10，以二倍扩容
    public class Main { 
    	static boolean isMirror;//记录是否为“镜像”,类中变量默认值为flase
    	static Vector<Integer> pre = new Vector<Integer>();//用于存储前序遍历的结点值
    	static Vector<Integer> post = new Vector<>();//用于存储后序遍历的结点值，省略写法
    	public static void main(String[] args) {  
    		Scanner scan = new Scanner(System.in);
    		int N= scan.nextInt();
    		for (int i = 0; i < N; i++) { 
    			pre.add(scan.nextInt());
    		}
            getPost(0,N-1);
            //若后序遍历数组的长度与前序遍历数组的长度不同，先判断为镜像二叉搜索树
            if(post.size()!=N){ 
                isMirror = true;
                post.clear();//清空Vector集合
                getPost(0,N-1);
            }
            if(post.size()==N){ 
               System.out.println("YES");
                for(int i=0;i<N-1;i++){ 
                    System.out.print(post.get(i)+" ");
                }
                System.out.println(post.get(N-1));
            }else
                System.out.println("NO");
      }
        public static void getPost(int root,int tail){ 
            if(root>tail)
                return;//头节点不可大能大于尾节点
            //设置两个变量作为标识进行前序遍历
            int i=root +1;
            int j=tail;
            if(!isMirror){ 
                while(i<=tail&&pre.get(root)>pre.get(i)){ 
                    i++;//二叉树的左子树值均小于跟节点值
                }
                while(j>root&&pre.get(root)<=pre.get(j)){ 
                    j--;//二叉搜索树的右子树值均大于根节点值
                }
            }else{ //若为镜像则相反
                while(i<=tail&&pre.get(root)<=pre.get(i)){ 
                    i++;
                }
                while(j>root&&pre.get(root)>pre.get(j)){ 
                    j--;
                }
            }
            if(i-j!=1){ 
                return;
            }
            //遍历根节点的左子树和右子树
            getPost(root+1,j);//左子树
            getPost(i,tail);//右子树
            post.add(pre.get(root));//对后序遍历节点值进行存储
        }
    }

**关注公众号【轻松玩编程】回复关键字“电子书”，“计算机资源”，“Java从入门到进阶”，”JavaScript教程“，“算法”，“Python学习资源”，“人工智能”等即可获取学习资源。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYWh1YW5f_size_16_color_FFFFFF_t_70_pic_center 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYWh1YW5f_size_16_color_FFFFFF_t_70_pic_center]: /images/20230209/564b650078e24612a92dc76154ac6184.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYWh1YW5f_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230209/7d7d8a8cae0c4af7a9c53964e74d3558.png