中序遍历二叉搜索树，得到的值序列是有序序列。因此，中序遍历二叉树，访问某个节点的时候，如果出现了反序情况，那么表明该树不是二叉搜索树。

层序遍历完全二叉树，判断孩子是否存在，存在则进入状态1，不存在则进入状态0，则层序遍历完全二叉树满足状态机：s → 状态1 → 状态0 → e，其中状态1和状态0有自旋边。如果遍历二叉树时，出现状态0变成状态1的情况，那么表明该树不是完全二叉树。


import java.util.*;


public class Solution {
    /**
     * 二叉搜索树的全局顺序，-1表示由小到大，0表示全等，1表示由大到小。
     */
    private int order;

    /**
     * 中序遍历二叉搜索树，上一个被访问节点的值。
     */
    private int lastVal;

    /**
     * @param root TreeNode类 the root
     * @return bool布尔型一维数组
     */
    public boolean[] judgeIt(TreeNode root) {
        TreeNode p = root;
        int min = 0;
        int max = 0;
        while (p != null){
            min = p.val;

            p = p.left;
        }
        p = root;
        while (p != null){
            max = p.val;
            
            p = p.right;
        }
        order = Integer.signum(min - max);
        lastVal = min;

        boolean[] result = new boolean[2];
        result[0] = dfs(root);// 判断是否为二叉搜索树。
        result[1] = bfs(root);// 判断是否为完全二叉树。

        return result;
    }

    /**
     * 层序遍历二叉树，判断树是否为完全二叉树。当前孩子存在（即不为null）则表示①，不存在则表示零。
     * 完全二叉树满足状态机 s → ① → 零 → e。①和零有自旋边。
     * @param root
     * @return
     */
    private boolean bfs(TreeNode root) {
        if (root == null) return true;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);

        int lastState = 1;// 上一个状态值。
        while (!queue.isEmpty()){
            TreeNode currNode = queue.remove();

            if (currNode.left == null){
                lastState = 0;
            }
            else {
                if (lastState == 0) return false;// 当前状态是1（表示当前孩子存在），不能由上个状态0返回状态1。
                queue.add(currNode.left);
            }

            if (currNode.right == null){
                lastState = 0;
            }
            else {
                if (lastState == 0) return false;// 当前状态是1（表示当前孩子存在），不能由上个状态0返回状态1。
                queue.add(currNode.right);
            }
        }

        return true;
    }

    /**
     * 中序遍历二叉树，如果访问的节点值由小到大/由大到小，那么该二叉树是二叉搜索树。
     * @param root
     * @return
     */
    private boolean dfs(TreeNode root) {
        if (root == null) return true;

        if (!dfs(root.left)) return false;// 左子树不是二叉搜索树。

        // 访问当前节点
        int currOrder = Integer.signum(lastVal - root.val);// 局部顺序。-1表示由小到大，0表示全等，1表示由大到小。

        if (currOrder != 0 && order != currOrder) return false;// 左子树加当前节点不满足二叉搜索树的要求。
        // 准备访问下一个节点
        lastVal = root.val;

        // 左子树加当前节点已满足二叉搜索树的要求，由右子树最终判定整棵树是否为二叉搜索树。
        return dfs(root.right);
    }
}