题解 | #判断一棵二叉树是否为搜索二叉树和完全二叉树#

import java.io.*;
import java.util.*;

public class Main {
    static class Node{
        int value;
        Node left;
        Node right;

        public Node(int data){
            this.value=data;
        }
    }

    /*判断是否是搜索二叉树
    神级遍历(Morris)中序遍历    时间复杂度O(N),空间复杂度O(1)
    * */
    public static boolean isBST(Node head){
        if(head==null){
            return true;
        }
        boolean res=true;
        Node pre=null;
        Node cur=head;//当前访问顶点
        Node mostRight=null;
        while (cur != null) {
            mostRight=cur.left;
            //判断是否有左子树
            if (mostRight!=null){
                //找出左子树最右节点
                while (mostRight.right!=null&&mostRight.right!=cur){
                    mostRight=mostRight.right;
                }
                //左子树最右节点的right指针是否为null
                if(mostRight.right==null){
                    mostRight.right=cur;
                    cur=cur.left;
                    continue;
                }else {
                    mostRight.right=null;
                }
            }
            if(pre!=null&&pre.value>cur.value){
                res=false;
            }
            pre=cur;
            cur=cur.right;

        }
        return res;
    }
    /*判断是否为完全二叉树
    1、按层遍历，每层从左边到右边依次遍历
    2、如果当前节点有右节点，但是没有左节点，返回false
    3、如果当前节点并不是左右节点都有，那么之后的节点必须都是叶子节点，否则返回false
    4、遍历过程如果不返回false，最后则返回true
    * */
    public static boolean isCBT(Node head){
        if(head==null){
            return true;
        }
        Queue<Node>queue=new LinkedList<Node>();
        boolean leaf=false;
        Node l=null;
        Node r=null;
        queue.offer(head);
        while (!queue.isEmpty()){
            head=queue.poll();
            l=head.left;
            r=head.right;

            if((leaf&&(l!=null||r!=null))||(l==null&&r!=null)){
                return false;
            }
            if(l!=null){
                queue.offer(l);
            }
            if(r!=null){
                queue.offer(r);
            }else {
                leaf=true;
            }


        }

        return true;
    }


    public static Node createTree(Scanner in,int n){
        int rootValue=in.nextInt();
        Node root=new Node(rootValue);
        HashSet<Node> set=new HashSet<Node>();
        set.add(root);

        //n行读取
        for (int i = 0; i < n; i++) {
            int fatherValue= in.nextInt();
            int leftValue=in.nextInt();
            int rightValue=in.nextInt();
            //遍历
            for (Node e:set){
                //1、比较节点
                if(e.value==fatherValue){
                    //2、建立左右节点
                    Node left= leftValue==0?null:new Node(leftValue);
                    Node right= rightValue==0?null:new Node(rightValue);
                    e.left=left;
                    e.right=right;
                    //3、放入节点
                    if(leftValue!=0){
                        set.add(left);
                    }
                    if(rightValue!=0){
                        set.add(right);
                    }
                    //4、remove
                    set.remove(e);
                    break;
                }
            }

        }


        return root;
    }

    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        Node root=createTree(in,n);

        boolean result1=isBST(root);
        System.out.println(result1);
        boolean result2=isCBT(root);
        System.out.println(result2);
    }
}