[NC]60. 判断一棵二叉树是否为搜索二叉树和完全二叉树

🚩传送门：牛客题目

题目

给定一棵二叉树，已知其中的节点没有重复值，请判断该二叉树是否为搜索二叉树和完全二叉树。
输出描述：分别输出是否为搜索二叉树、完全二叉树。
注意：空子树我们认为同时符合搜索二叉树和完全二叉树。

示例2

输入：{1,#,2} 返回值：{true,false} 说明：由于节点的右儿子大于根节点，无左子树，所以是搜索二叉树但不是完全二叉树

解题思路：递归+层次遍历

1. 递归判断是否是搜索二叉树
2. 利用层次遍历判断是否是完全二叉树

复杂度分析

时间复杂度：， 为二叉树的节点个数。

  - 二叉树的每个节点被访问两次，因此时间复杂度为 ![](https://cdn.nlark.com/yuque/__latex/7ba55e7c64a9405a0b39a1107e90ca94.svg#card=math&code=O%28n%29&height=23&id=X3zRr)

空间复杂度：， 为二叉树的节点个数。

  - 队列最多存储 ![](https://cdn.nlark.com/yuque/__latex/ea02f5f09fa635e33c4857ec99404ad9.svg#card=math&code=2n-1&height=23&id=tURpv) 个节点，因此需要额外的 ![](https://cdn.nlark.com/yuque/__latex/7ba55e7c64a9405a0b39a1107e90ca94.svg#card=math&code=O%28n%29&height=23&id=ncJyW) 的空间。

我的代码

public class Solution {
    public boolean isSerachTreeBST(TreeNode root,int low,int hight){
        if(root==null)
            return true;
        if(root.val>hight||root.val<low)
            return false;
        return isSerachTreeBST(root.left,low,root.val)
            && isSerachTreeBST(root.right,root.val,hight);
    }
    public boolean isAllTreeBST(TreeNode root){
        if(root==null)return true;
        LinkedList<TreeNode> q=new LinkedList<>();
        q.addLast(root);
         //当左右子树中出现一个空缺,说明后面不能再有结点
        while(q.peek()!=null){
            TreeNode node=q.poll();
            q.addLast(node.left);
            q.addLast(node.right);
        }
        while (!q.isEmpty()&&q.peek()==null)
            q.poll();
        return q.isEmpty();
    }
    public boolean[] judgeIt (TreeNode root) {
        // write code here
        boolean[]ans=new boolean[]{true,true};
        if(root==null)return ans;
        ans[0]=isSerachTreeBST(root,Integer.MIN_VALUE,Integer.MAX_VALUE);
        ans[1]=isAllTreeBST(root);
        return ans;
    }
}