判断二叉树是否是二叉搜索树和完全二叉树

题目描述

给定一棵二叉树，已经其中没有重复值的节点，请判断该二叉树是否为搜索二叉树和完全二叉树。

示例1

输入

复制

{2,1,3}

返回值

复制

[true,true]

备注:

$n \leq 500000$

import java.util.*;
public class Solution {
    public boolean[] judgeIt (TreeNode root) {
        dfs(root);
        boolean flagFulll = judgeFull(root);
        return new boolean[]{flag,flagFulll};
    }
    
    Integer pre =null;
    boolean flag = true;
    // 判断是否是二叉搜索树
    public void dfs(TreeNode root){
        if(root==null)return;
        dfs(root.left);
        if(pre == null){
            pre = root.val;
        }else{
            if(root.val < pre){
                flag = false;
            }
            pre = root.val;
        }
        dfs(root.right);
    }
    // 判断二叉树是否是完全二叉树
    public boolean judgeFull(TreeNode root){
        if(root==null)return true;
        Queue <TreeNode> queue =new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0;i<size;i++){
                TreeNode node = queue.poll();
                // 如果当前节点为空，那么它后面的所有节点都应该是空的，如果不是空的，那么说明不是完全二叉树
                if(node == null){
                    while(!queue.isEmpty()){
                        node = queue.poll();
                        if(node!=null)return false;
                    }
                    // 如果后面的所有节点都是空的,那么返回true;
                    return true;
                }
                
                queue.offer(node.left);
                queue.offer(node.right);
            }
        }
        return true;
    }
}

赏

谢谢你请我吃糖果

微信