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

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) {
        if(root == null || (root.left == null && root.right == null)) return new boolean[]{true , true} ;
        boolean[] res = new boolean[2] ;
        res[0] = isSearchTree(root) ;
        res[1] = isCompleteTree(root) ;
        return res ;
    }
    public boolean isSearchTree(TreeNode root) {
        if(root == null || ((root.left == null && root.right == null))) return true ;
        //寻找左子树的最大值
        int lMax = -1 ;
        if(root.left != null) {
            TreeNode t = root.left ;
            while(t.right != null) {
                t = t.right ;
            }
            lMax = t.val ;
        }
        //寻找右子树的最小值
        int rMin = 500001 ;
        if(root.right != null) {
            TreeNode t = root.right ;
            while(t.left != null) {
                t = t.left ;
            }
            rMin = t.val ;
        }
        if(root.val > lMax && root.val < rMin) {
            return isSearchTree(root.left) && isSearchTree(root.right) ;
        } else {
            return false ;
        }
    }
    
    public boolean isCompleteTree(TreeNode root) {
        if(root == null) return true ;
        Queue<TreeNode> que = new LinkedList<>() ;
        que.offer(root) ;
        TreeNode t = null ;
        boolean firstLeave = false ;//是否出现 缺右
        while(!que.isEmpty()) {
            t = que.poll() ;
            if(t.left == null && t.right != null) return false ;
            if(firstLeave && !(t.left == null && t.right == null)) {
                return false ;
            }
            //只要第一次出现 缺右现象，后面的节点都必须是 叶子结点
            if(firstLeave == false && t.right == null) {
                firstLeave = true ;
            } 
            if(t.left != null) que.offer(t.left) ;
            if(t.right != null) que.offer(t.right) ;
        }
        return true ;
    }
}