【算法】搜索二叉树，完全二叉树，平衡二叉树的判断

    /// 判断是否是搜索二叉树，就要判断是否符合左子树 < 根节点，右子树 > 根节点
    /// 而该树是搜索二叉树，那么其中序遍历必然是升序的，因此在非递归的中序遍历基础上
    /// 修改，只需对比当前数比上一个数都大，即可判断是否是搜索二叉树
    public static boolean isBST(Node head) {
        if (head == null) {
            return true;
        }
        int pre = Integer.MIN_VALUE;
        Stack<Node> stack = new Stack<Node>();
        while (!stack.isEmpty() || head != null) {
            if (head != null) {
                stack.push(head);
                head = head.left;
            }else {
                head = stack.pop();
                if (head.value < pre) {
                    return false;
                }
                pre = head.value;
                head = head.right;
            }
        }
        return true;
    }

    /// 判断是否是满二叉树
    /// 1、如果一个树，有右孩子，没有左孩子，那么必然不是满二叉树
    /// 2、如果一个树，只有左孩子，那么后续节点必然都是叶子节点，才能是满二叉树
    public static boolean isCBT(Node head) {
        if (head == null) {
            return true;
        }
        Queue<Node> queue = new LinkedList<Node>();
        queue.offer(head);
        boolean isLeaf = false;
        while(!queue.isEmpty()) {
            head = queue.poll();
            if (isLeaf) {
                if (head.left != null || head.right != null) {
                    return false;
                }
            }
            // 只有右孩子，没有左孩子，必然不是满二叉树
            if (head.left == null && head.right != null) {
                return false;
            }
            if (head.left != null && head.right == null) {
                // 开启后续节点必为叶节点的判断
                isLeaf = true;
            }
            if (head.left != null) {
                queue.offer(head.left);
            }
            if (head.right != null) {
                queue.offer(head.right);
            }
        }
        return true;
    }

    public static boolean isBalance(Node head) {
        boolean[] res = new boolean[1];
        res[0] = true;
        getHeight(head, res);
        return res[0];
    }

    public static int getHeight(Node head, boolean[] res) {
        if (head == null) {
            return 0;
        }
        int lh = getHeight(head.left, res);
        if (!res[0]) {
            return 0;
        }
        int rh = getHeight(head.right, res);
        if (!res[0]) {
            return 0;
        }
        if (Math.abs(lh - rh) > 1) {
            res[0] = false;
        }
        return Math.max(lh, rh) + 1;
    }