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

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[] ret = new boolean[2];
        boolean search = isSearchTree(root);
        boolean level = isLevel(root);
        ret[0] = search;
        ret[1] = level;
        return ret;
    }
    
     // 层序遍历
    private boolean isLevel(TreeNode root) {
         if (root == null) {
            return true;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            int m = 0;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node == null) {
                    m++;
                }
                if (m == size) {
                    return true;
                }
                if (node == null && queue.peek() != null) {
                    return false;
                }

                if (node != null) {
                    queue.offer(node.left);
                    queue.offer(node.right);
                } else {
                    queue.offer(null);
                    queue.offer(null);
                }
            }
        }
        return true;
    }
    
    int last = -1;

    // 中序遍历，如果是二叉搜索树，则是升序。
    private boolean isSearchTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        boolean left = isSearchTree(root.left);
        if (last >= root.val) {
            return false;
        }
        last = root.val;
        boolean right = isSearchTree(root.right);
        return left && right;
    }
}