（一）搜索二叉树 BST

（一）搜索二叉树 BST

【搜索二叉树 BST 概念】对于二叉树的任意一棵子树，其左子树上的所有结点的值小于该子树的根节点的值，而其右子树上的所有结点的值大于该子树的根结点的值，并且整棵树上任意两个结点的值不同（重复的结点的值可以通过 List 的形式进行存放）。

【解答方案】 根据二叉树的中序遍历看是否递增 根据定义，搜索二叉树的中序遍历打印将是一个升序序列。因此我们可以利用二叉树的中序遍历的非递归方式，比较中序遍历时相邻两个结点的大小，只要有一个结点的值小于其后继结点的那就不是搜索二叉树。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    Integer preValue = null;
    public boolean isValidBST(TreeNode root) {
        if(root == null){
            return true;
        }
        if(isValidBST(root.left)){
            if(preValue != null && preValue >= root.val){
                return false;
            }
            preValue = root.val;
            return isValidBST(root.right);
        }
        return false;
    }
}

（二）完全二叉树 CBT

【完全二叉树 CBT 概念】如果二叉树上某个结点有右孩子无左孩子则一定不是完全二叉树；如果二叉树上某个结点有左孩子而没有右孩子，那么该结点所在的那一层上，该结点左侧的所有结点应该都是叶子结点，否则不是完全二叉树。

【解答方案】 将二叉树按层遍历，如果结点有右孩子但是没有左孩子则一定不是完全二叉树，如果不符合上面，则接着判断是否是有左孩子没有右孩子或者是两个都没有，如果是这种情况则该结点下面的所有节点都必须是叶子结点；否则就不是完全二叉树；

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isCompleteTree(TreeNode root) {
        if(root == null){
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        boolean leaf = false;
        TreeNode left = null;
        TreeNode right = null;
        queue.offer(root);
        while(!queue.isEmpty()){
            root = queue.poll();
            left = root.left;
            right = root.right;
            if((leaf && (left != null || right != null)) || (left == null && right != null)){
                return false;
            }
            if(left != null){
                queue.offer(left);
            }
            if(right != null){
                queue.offer(right);
            }else{
             // 左等于空或者右等于空 则开启。因为上面代码已经去掉左等于空的情况，因此这里只需要判断右是否为空；
                leaf = true;
            }
        }
        return true;
    }
}