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

方法一（递归+广度优先搜索）

1.题意整理

• 给定一颗二叉树，树中没有重复节点。
• 判断该树是否是二叉搜索树、是否是完全二叉树。

2.思路整理

判断搜索二叉树（BST）： 考虑搜索二叉树的定义，每一个节点的值应该大于等于左子树中的最大值，小于等于右子树中的最小值。所以我们可以利用递归遍历每一个节点，如果某个节点不满足定义，则不合法，直接返回false。

图解展示：

判断完全二叉树（CST）： 完全二叉树是严格按照顺序从上到小，从左到右排列的二叉树，只有上一层满了，才可以在下一层从左到右开始排。所以可以利用层序遍历模拟这个过程，如果遍历的过程中，发现之前出现过空节点，而当前节点不是叶子节点，则不合法。

图解展示：

3.代码实现

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) {
        return new boolean[]{BST(root,Integer.MIN_VALUE,Integer.MAX_VALUE),CST(root)};
    }
    //判断是否为搜索二叉树,left表示当前左子树节点最大值，right表示当前右子树节点最小值
    private boolean BST(TreeNode root,long left,long right){
        //递归终止条件
        if(root==null) return true;
        //如果当前节点小于等于左子树节点最大值或者大于等于右子树节点最小值，则不合法
        if(root.val<=left||root.val>=right){
            return false;
        }
        //考虑左子树时，left不变(left可能不变，也可能变小，但是变小的情况仍然可以用原来的left校验合法性，所以left可以保持不变)，对应右子树由于要考虑当前节点，right变为root.val,同理考虑右子树
        return BST(root.left,left,root.val)&&BST(root.right,root.val,right);
    }
    //判断是否为完全二叉树
    private boolean CST(TreeNode root){
        if(root==null) return true;
        //新建队列，用于层序遍历
        LinkedList<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        //判断是否走过空节点
        boolean reachNull=false;
        while(!queue.isEmpty()){
            int n=queue.size();
            for(int i=0;i<n;i++){
                //当前层节点
                TreeNode node=queue.poll();
                if(node.left!=null){
                    //如果当前左子节点不为空，并且走过空节点，则不合法
                    if(reachNull){
                        return false;
                    }
                    //左子节点入队列
                    queue.offer(node.left);
                }
                else{
                    reachNull=true;
                }
                if(node.right!=null){
                    //如果当前右子节点不为空，并且走过空节点，则不合法
                    if(reachNull){
                        return false;
                    }
                    //右子节点入队列
                    queue.offer(node.right);
                } 
                else{
                    reachNull=true;
                }
            }
        }
        return true;
    }
}

4.复杂度分析

• 时间复杂度：两个函数都需要遍历树中所有节点，所以时间复杂度为$O(n)O(n)$。
• 空间复杂度：判断搜索二叉树时，最坏情况下，递归栈深度为n，判断完全二叉树时，需要借助大小为n的队列，所以空间复杂度是$O(n)O(n)$。