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

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
        boolean[] res = new boolean[2];
        res[0] = isSearchTree(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
        res[1] = isAllTree(root);
        return res;
    }

    // 判断是否是二叉搜索树，主要利用二叉搜索树的特性，左右边界
    public boolean isSearchTree(TreeNode root, int left, int right) {
        if(root == null) return true;
        if(root.val <= left || root.val >= right) return false;
        return isSearchTree(root.left, left, root.val) && isSearchTree(root.right, root.val, right);
    }

    // 判断是否是完全二叉树
    public boolean isAllTree(TreeNode root) {
        if(root == null) return true;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        // 用来标记是否已经出现左右子树不双全的节点
        boolean flag = false;
        while(!q.isEmpty()) {
            int sz = q.size();
            for(int i = 0; i < sz; i++) {
                TreeNode node = q.poll();
                // 如果左子树为空，右子树不为空，则不是完全二叉树
                if(node.left == null && node.right != null) {
                    return false;
                }
                // 出现过不双全节点后，后续的节点都必须是叶子节点
                if(flag && (node.left != null || node.right != null)) {
                    return false;
                }
                if(node.left == null || node.right == null) {
                    flag = true;
                }
                if(node.left != null) q.add(node.left);
                if(node.right != null) q.add(node.right);
            
            }
        }
        return true;
    }
}