题意整理

  • 给定一颗二叉树，判断该二叉树是否为搜索二叉树和完全二叉树。
  • 二叉树中节点无重复值。

方法一（递归+层序遍历）

1.解题思路

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

图解展示： alt

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

图解展示： alt

2.代码实现

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)};
    }
    //判断是否为搜索二叉树
    private boolean BST(TreeNode root,long left,long right){
        //递归终止条件
        if(root==null) return true;
        //如果当前节点小于等于左子树节点最大值或者大于等于右子树节点最小值，则不合法
        if(root.val<=left||root.val>=right){
            return false;
        }
        //考虑左子树时，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;
    }
}

3.复杂度分析

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

方法二（中序遍历+层序遍历）

1.解题思路

判断搜索二叉树（BST）： 如果中序遍历搜索二叉树，则过程中的节点一定是从小到大排列的，利用这个特点，检查遍历过程中的每一个节点，如果不满足，则不合法。

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

2.代码实现

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布尔型一维数组
     */
    //中序遍历中当前节点的前一个节点对应的值
    int pre=Integer.MIN_VALUE;
    
    public boolean[] judgeIt (TreeNode root) {
        return new boolean[]{BST(root),CST(root)};
    }
    //判断是否为搜索二叉树
    private boolean BST(TreeNode root){
        //递归终止条件
        if(root==null) return true;
        //判断左子树
        if(!BST(root.left)) return false;
        //如果当前节点值小于等于前一个，说明不是搜索二叉树
        if(root.val<=pre) return false;
        pre=root.val;
        //判断右子树
        return BST(root.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;
    }
}

3.复杂度分析

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