思路:

从题中给出的有效信息：

  • 二叉树是否为搜索二叉树和完全二叉树

故此 二叉树 搜索树采用递归的方式解决，完全二叉树使用bfs对其进行求解

方法一：递归+广度优先遍历

具体做法：
搜索树：使用递归的方式进行求解，判断该二叉树的左子树不为空，则左子树上所有节点的值均小于的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左右子树也为二叉搜索树。
完全树：使用宽度优先进行遍历求解，判断遇到左右孩子不双全的节点并且该节点不是叶子节点，不是完全二叉树；当遇到节点的左孩子为空且右孩子不为空的时候，不是完全二叉树；

具体过程如下图所示：
搜索树：
图片说明 

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[] res = new boolean[2];

        res[0] = isSerachTreeBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
        res[1] = isAllTreeBST(root);

        return res;

    }
     //判断搜索树
    public boolean isSerachTreeBST(TreeNode root, long left, long right){
        if(root == null)return true;

        if(root.val <= left || root.val >= right)return false;

        return isSerachTreeBST(root.left, left, root.val) && isSerachTreeBST(root.right, root.val, right);
    }
    //判断完全树
    public boolean isAllTreeBST(TreeNode root){
        if(root == null) return true;
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode left = null;
        TreeNode right = null;
        boolean flag = false; //标记是否遇到节点不双全的节点
        while(!queue.isEmpty()){
            root = queue.poll();
            left = root.left;
            right = root.right;
            //遇到左右孩子不双全的节点并且该节点不是叶子节点的时候就不是完全二叉树  //左孩子为空并且右孩子不为空的时候不是完全二叉树
            if((flag && !(left == null && right == null)) || (left == null && right != null)){
                return false;
            }
            if(left != null)    queue.offer(left);
            if(right != null)   queue.offer(right);
            if(left == null || right == null)   flag = true;
        } 
        return true;
    }
}

复杂度分析：

  • 时间复杂度：O(N) n 为二叉树的节点数。
  • 空间复杂度：O(N) 搜索树和完全树申请了两次空间

方法二：中序遍历+广度优先遍历

具体做法：
搜索树：中序遍历时，判断当前节点是否大于中序遍历的前一个节点，如果大于，说明满足 搜索树，继续遍历；否则直接返回 false。
完全树：使用宽度优先进行遍历求解，判断遇到左右孩子不双全的节点并且该节点不是叶子节点，不是完全二叉树；当遇到节点的左孩子为空且右孩子不为空的时候，不是完全二叉树；

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[] res = new boolean[2];

        res[0] = isSerachTreeBST(root);
        res[1] = isAllTreeBST(root);

        return res;

    }

    long pre = Long.MIN_VALUE;
    //判断搜索树
    public boolean isSerachTreeBST(TreeNode root){
        if(root == null)return true;
        // 访问左子树
        if (!isSerachTreeBST(root.left)) {
            return false;
        }
        // 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回 false；否则继续遍历。
        if (root.val <= pre) {
            return false;
        }
        pre = root.val;
        // 访问右子树
        return isSerachTreeBST(root.right);   
    }
     //判断完全树
    public boolean isAllTreeBST(TreeNode root){
        if(root == null) return true;
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode left = null;
        TreeNode right = null;
        boolean flag = false; //标记是否遇到节点不双全的节点
        while(!queue.isEmpty()){
            root = queue.poll();
            left = root.left;
            right = root.right;
            //遇到左右孩子不双全的节点并且该节点不是叶子节点的时候就不是完全二叉树  //左孩子为空并且右孩子不为空的时候不是完全二叉树
            if((flag && !(left == null && right == null)) || (left == null && right != null)){
                return false;
            }
            if(left != null)    queue.offer(left);
            if(right != null)   queue.offer(right);
            if(left == null || right == null)   flag = true;
        } 
        return true;
    }
}

复杂度分析：

  • 时间复杂度：O(N) n 为二叉树的节点数。
  • 空间复杂度：O(N) 搜索树和完全树申请了两次空间