NC60：判断一棵树是否为搜索二叉树和完全二叉树

• 二叉搜索树：每个节点左边节点小于右边节点，左子树的最大值一定小于根节点，小于右子树的最大值；通过中序遍历，严格递增

• 完全二叉树：层序遍历，除了最后的一层，每层都是满的

  import java.util.*;
  /*
  * public class TreeNode {
  *   int val = 0;
  *   TreeNode left = null;
  *   TreeNode right = null;
  * }
  */
  public class Solution {
    /*
     * @param root TreeNode类 the root
     * @return bool布尔型一维数组
     */
    public boolean[] judgeIt (TreeNode root) {
        // write code here
        if(root==null){
            return new boolean[]{false,false};
        }
        ArrayList<Integer> list = new ArrayList<>();
        midsearch(root,list);
        boolean flag1=true;
        for(int i=1;i<list.size();i++){
            if(list.get(i)<list.get(i-1)){
                flag1=false;
                break;
            }
        }
        boolean flag2=isCompleteTree(root);
        return new boolean[]{flag1,flag2};
    }
  
    public void midsearch(TreeNode root,ArrayList<Integer> list){
         // 中序遍历
        if(root==null){
            return ;
        }
        midsearch(root.left,list);
        list.add(root.val);
        midsearch(root.right,list);
    }
  
    public boolean isCompleteTree(TreeNode root){
        // 判断一棵树是否为完全二叉树，层序遍历，一旦出现null
        //则队列中剩余的节点必须为叶子节点
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            if(cur.left==null){
                // 遍历每个节点
                if(cur.right!=null){
                    return false;
                }
                while(!queue.isEmpty()){
                    TreeNode p=queue.poll();
                    if(p.left!=null || p.right!=null){
                        return false;
                    }
                }
                return true;
            }
            else{
                queue.add(cur.left);
            }
            if(cur.right==null){
                while(!queue.isEmpty()){
                    TreeNode q=queue.poll();
                    if(q.right!=null || q.left!=null){
                        return false;
                    }
                }
                return true;
            }
            else{
                queue.add(cur.right);
            }
        }
        return true;
    }
  }

// 搜索二叉树：中序遍历是左中右，而搜索二叉树就是 左 < 中 < 右，
//稍加改动，将弹出的值用一个变量保存（可以初始化为系统最小值），比较大小
    public static boolean isBST (Node head) {
        if (head == null) {
            return true;
        }
        Stack<Node> stack = new Stack<Node>();
        int pre = Integer.MIN_VALUE;
            // 这里定义一个系统最小数，用于下面的和前面的数比较
        while (!stack.isEmpty() || head != null) {
            if (head != null) {
                stack.push(head);
                head = head.left;
            } else {
                head = stack.pop();
    // --------这里本来是中序遍历打印节点的地方，这里改成和前面的节点值比较，
    //如果大于，直接返回false，否则迭代------------
                if (head.value < pre) { 
    // 搜索二叉树默认节点不相等，若相等，就会变成同一个节点
                    return false;
                } else {
                    pre = head.value;
                }
    // -------------------------------------------
                head = head.right;
            }
        }
        return true;
    }

// 这里是判断二叉树是否是完全二叉树，
// 这里用到两个技巧：1、用queue来层级遍历，2、每个节点的左右节点有四种情况：左空右空，左有右空，左空右有，左有右有
// 其中如果左空右有，直接返回false，如果左空右空，左有右空，那么接下来的节点一定是叶节点
    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);// 想queue里面增加元素
        while(!queue.isEmpty()){
            head=queue.poll();
            l=head.left;
            r=head.right;
   /**
   * 判断完全二叉树的两个标准：
   *①某个节点有右孩子没有左孩子，则不是完全二叉树
   *②满足①的条件下，某个节点没有右孩子有左孩子，或者没有左右孩子时，
   * 后面遇到的所有节点必须是叶节点。
   **/
        // 右节点不为空但是左节点为空，直接返回false    
        if((leaf&&(l!=null  || r!=null)) || (l==null&&r!=null)){
            return false;
        }

        // 其他情况，往queue里面存节点
        if (l != null) {
                queue.offer(l);
            }
            if (r != null) {
                queue.offer(r);
            }
            if(l==null || r==null){
                leaf=true;
            }
        }
        return true;
    }