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

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) {
        boolean[] result = new boolean[2];

        result[0] = isTwoSearchTree(root, null, null);

        result[1] = isFullTree(root);

        return result;
    }

    // 是否为二叉搜索树
    public boolean isTwoSearchTree(TreeNode root, Integer min, Integer max){

        if (root == null) {
            return true;
        }

        // 如果root值小于最低项则不是搜索二叉树
        if (min != null && root.val <= min) {
            return false;
        }

        // 如果root值大于最高项，也不是二叉搜索树
        if (max != null && root.val >= max) {
            return false;
        }

        boolean leftFlg = isTwoSearchTree(root.left, min, root.val);
        boolean rightFlg = isTwoSearchTree(root.right, root.val, max);

        return leftFlg && rightFlg;
    }


    // 验证是否为完全二叉树
    public boolean isFullTree(TreeNode root){

        if(root == null){
            return false;
        }

        LinkedList<TreeNode> queue = new LinkedList();
        queue.offer(root);

        while(!queue.isEmpty()){

            TreeNode temp = queue.poll();

            if (temp != null) {
                queue.offer(temp.left);
                queue.offer(temp.right);
            } else {

                // 如果节点为nul,则去判断后面的节点中是否还存在不为null，
                // 如果还存在不为null的节点，则不是完全二叉树
                // 因为完全二叉树，要么叶子节点都是满的，要么都聚集在左节点上，所以聚集在左节点上，所有的null都在最后面。
                while (!queue.isEmpty()) {

                    TreeNode leafNode = queue.poll();

                    if (leafNode != null) {
                        return false;
                    }
                }
            }
        }

        return true;
    }
}