判断是不是完全二叉树_

Java

17c89

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

/**
 * NC198 判断是不是完全二叉树
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    public boolean isCompleteTree (TreeNode root) {
        return levelOrder(root);
    }

    /**
     * 层序遍历
     * @param root
     * @return
     */
    private boolean levelOrder(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        TreeNode tNode;
        while(queue.peek() != null){
            tNode = queue.poll();
            queue.offer(tNode.left);
            queue.offer(tNode.right);
        }

        while(!queue.isEmpty() && queue.peek()==null){
            queue.poll();
        }

        return queue.isEmpty();
    }
}

发表于 2025-01-14 13:04:47 回复(0)

Java

୧⍢⃝୨

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    public boolean isCompleteTree (TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();

        int n = 1;
        q.offer(root);

        while (!q.isEmpty()) {
            int size = q.size();
            if (size == (int)Math.pow(2, n - 1)) {
                boolean flag = false;
                while (size > 0) {
                    TreeNode node = q.poll();
                    if(node.left==null && node.right!=null){
                        return false;
                    }
                    if (flag && (node.left != null || node.right != null)) {
                        return false;
                    }
                    if (!flag && (node.left == null || node.right == null)) {
                        flag = true;
                    }
                    if (node.left != null) {
                        q.offer(node.left);
                    }
                    if (node.right != null) {
                        q.offer(node.right);
                    }
                    size--;
                }
                n++;
            } else {
                while (size > 0) {
                    TreeNode node = q.poll();
                    if (node.left != null || node.right != null) {
                        return false;
                    }
                    size--;
                }
            }
        }
        return true;
    }
}

发表于 2024-09-09 10:10:55 回复(0)

Java

牛客348570162号

    // 用层序遍历
    // 将null也放入队列。如果为完全二叉树，那么获取到null时，队列中的节点都为null。
    // 如果存在非null节点，说明不是完全二叉树
    public boolean isCompleteTree (TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(true){
            TreeNode t = queue.poll();
            if(t == null) break; //当其中一个节点为null时退出
            TreeNode l = t.left,r = t.right;
            queue.add(l);
            queue.add(r);
        }
        // 检查剩下的节点中是否有非null节点。
        while(!queue.isEmpty()){
            TreeNode t = queue.poll();
            if(t != null) return false;
        }
        return true;
    }

发表于 2024-08-27 16:43:42 回复(0)

Java

人间水长东

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    public boolean isCompleteTree (TreeNode root) {
        // write code here

        // 算法的时间复杂度O(N)，额外空间复杂度O(N)

        // 1.数据准备
        // 1.1 创建队列，用于层序遍历
        Queue<TreeNode> queue = new LinkedList<>();
        // 1.2 创建数组，用于存储结点序号及其本身（同时保留结点的父子关系），因为有序所以方便遍历
        LinkedList<TreeNode> list = new LinkedList<>();
        // 1.3 创建哈希表，用于根据结点查询其序号
        HashMap<TreeNode, Integer> map = new HashMap<>();

        // 2.层序遍历，写入数据结构
        // 2.1 头结点先入队
        queue.add(root);
        // 2.2 利用队列层序遍历
        int number = 0;
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            // 2.3 分配编号，写入数据结构
            list.add(cur);
            map.put(cur, number);
            // 2.4 子节点入队
            if (cur.left != null) {
                queue.add(cur.left);
            }
            if (cur.right != null) {
                queue.add(cur.right);
            }
            // 2.5序号自增
            number++;
        }

        // 3.验证完全二叉树 - i -> 2i + 1 / 2i + 2
        for (TreeNode cur : list) {
            // 3.1 通过HashMap获得当前结点的序号
            int curNo = map.get(cur);
            // 3.2 分别获得其左右子结点，验证序号是否满足2i + 1 / 2i + 2
            if (cur.left != null) {
                int leftNo = map.get(cur.left);
                if (leftNo != (2 * curNo + 1)) {
                    // 3.3 若当前结点不满足，则直接返回false
                    return false;
                }
            }
            if (cur.right != null) {
                int rightNo = map.get(cur.right);
                if (rightNo != (2 * curNo + 2)) {
                    // 3.3 若当前结点不满足，则直接返回false
                    return false;
                }
            }
        }
        // 3.4 若每个结点都满足，则返回true
        return true;
    }
}

发表于 2024-08-05 01:07:15 回复(0)

Java

我也今晚打老虎

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    public boolean isCompleteTree (TreeNode root) {
        returnType res = judge(root);
        return res.isCT;
    }
    public returnType judge(TreeNode root){
        // 递归向左右子树索要信息：1. 左右子树节点个数; 2. 左右子树的高度，相差不能大于1 3. 是不是CompleteTree (后序遍历)
        returnType res = new returnType(0, 0, false); 
        if(root == null){
            res.isCT = true;
            return res;
        }
        returnType leftRes = judge(root.left);
        returnType rightRes = judge(root.right);
        res.count = (leftRes.count + rightRes.count) + 1;
        res.depth = Math.max(leftRes.depth, rightRes.depth) + 1;
        // System.out.println(rightRes.count);
        if(leftRes.count < rightRes.count) return res; // 左子树节点个数小于右子树
        if(!leftRes.isCT || !rightRes.isCT) return res;
        if(Math.abs(leftRes.depth - rightRes.depth) > 1) return res;
        res.isCT = true;
        return res;
    }
    public class returnType{
        int count = 0;
        int depth = 0;
        boolean isCT = false;
        public returnType(int count, int depth, boolean isCT){
            this.count = count;
            this.depth = depth;
            this.isCT = isCT;
        }
    }
}

编辑于 2024-04-11 18:06:40 回复(0)

Java

不讲武德的芝士很年轻

public class Solution {

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

*

* @param root TreeNode类

* @return bool布尔型

*/

public boolean isCompleteTree (TreeNode root) {

// write code here

if (root == null)

return true;

LinkedList<TreeNode> queue = new LinkedList<>();

boolean leaf = false;

queue.add(root);

while (!queue.isEmpty()) {

root = queue.poll();

TreeNode r = root.right;

TreeNode l = root.left;

if ((l == null && r != null) || (leaf && (l != null || r != null))) {

return false;

}

if (l != null) {

queue.add(l);

}

if (r != null) {

queue.add(r);

}

if (l == null || r == null) {

leaf = true;

}

return true;

}

编辑于 2024-04-08 15:51:54 回复(0)

Java

感性的小健求实习

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    public boolean isCompleteTree (TreeNode root) {
        // write code here
        if (root == null ) return false;
        return pre(root);
    }
    boolean pre (TreeNode node) {
        boolean isLeftOK = true;
        boolean isRightOK = true;
        if (node.left == null && node.right == null) return true;
        if (node.left != null) {
            if (node.right != null) {
                isLeftOK = pre(node.left);
                isRightOK = pre(node.right);
            } else {
                if (node.left.left != null || node.left.right != null) return false;
            }
        }
        if (node.right != null) {
            if (node.left == null) return false;
            if (node.left.left == null && (node.right.right != null ||
                                           node.right.left != null)) {
                return false;
            }
            if (node.left.right == null && (node.right.right != null ||
                                            node.right.left != null)) {
                return false;
            }
        }
        return isLeftOK && isRightOK;
    }
}

没用大家都在用的队列什么的，就是普通的一个屎山代码。

编辑于 2024-02-26 16:29:05 回复(0)

Java

BlueProtocol

使用层序遍历二叉树，然后看看是左子树是否为空，如果是空，通过判断遍历到右子树的时候直接返回false。

    public boolean isCompleteTree (TreeNode root) {
        // write code here
        if(root == null) return true;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        boolean isHasLeft = true;
        while(!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            if(poll == null) isHasLeft = false;
            else{
                if(isHasLeft == false) return isHasLeft;
                queue.add(poll.left);
                queue.add(poll.right);
            }
        }
        return true;
    }

发表于 2023-11-12 11:49:00 回复(0)

Java

李克雷

public class Solution {
    /**
     * 给定一个二叉树，确定他是否是一个完全二叉树。
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    public boolean isCompleteTree (TreeNode root) {
        if (null == root) {
            return true;
        }
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        while (!que.isEmpty()) {
            TreeNode curr = que.poll();
            if (null == curr) {
                break;
            }
            que.offer(curr.left);
            que.offer(curr.right);
        }
        while (!que.isEmpty()) {
            if (que.poll() != null) {
                return false;
            }
        }
        return true;
    }

}

发表于 2023-10-18 18:15:46 回复(1)

Java

DDwu

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    public boolean isCompleteTree (TreeNode root) {
        // write code here
        if (root == null) return true;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        boolean iscompleted = false;
        while (!q.isEmpty()) {
            TreeNode temp = q.poll();
            if (temp == null) {
                iscompleted = true;
                continue;
            }
            if (iscompleted) {
                return false;
            }
            q.offer(temp.left);
            q.offer(temp.right);
        }
        return true;
    }
}

发表于 2023-07-27 14:57:48 回复(0)

Java

做则必成的勇气和信心

public boolean isCompleteTree (TreeNode root) {
        if(root==null) return true;
        Deque<TreeNode> qu=new LinkedList<>();
        qu.offer(root);
        boolean flag=false;//flag表示需不需要后面都是叶子节点
        while(!qu.isEmpty()){
            int level=qu.size();
            TreeNode Node=qu.poll();
            if(Node.right!=null&&Node.left==null){//有右孩子  没有左孩子  直接false
                return false;
            }
            if(flag&&(Node.left!=null||Node.right!=null)){//如果flag是true（必须是叶子节点）
                return false;
            }
            //遇到第一个 左右孩子节点不全的节点  flag变为true
            if(Node.left==null||Node.right==null){
                flag=true;
            }
            if(Node.left!=null) qu.offerLast(Node.left);
            if(Node.right!=null) qu.offerLast(Node.right);
            
        }
        return true;
    }

发表于 2023-07-13 21:45:24 回复(0)

Java

ZhanHeng

import java.util.*;


public class Solution {
    public boolean isCompleteTree (TreeNode root) {
        if (root == null) {
            return false;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);

        boolean flag = false;
        // 层次遍历
        while (!queue.isEmpty()) {
            int levelNumber = queue.size();
            for (int i = 0; i < levelNumber; i++) {
                TreeNode left = queue.peek().left;
                TreeNode right = queue.peek().right;
                // 若左节点为空,右节点不为空, 一定非法。则直接false
                if (left == null && right != null) {
                    return false;
                }

                // 出现空节点 且 后续还出现非空节点的话就不满足完全二叉树，就直接false
                if (flag && (left != null || right != null)) {
                    return false;
                }

                // 记录非法的情况：
                if ((left != null && right == null)
                        || (left == null && right == null)) {
                    flag = true;
                }

                if (left != null) {
                    queue.offer(left);
                }
                if (right != null) {
                    queue.offer(right);
                }
                queue.poll();
            }
        }
        return true;
    }
}

发表于 2022-11-18 12:20:51 回复(1)

Java

dynamo1

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    private int index = 0, count = 0;
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    public boolean isCompleteTree (TreeNode root) {
        // write code here
        if (root == null) {
            return false;
        }
      //  doDfs(root, 1);
       // return count == index;
       return doIsCompleteTree(root);
    }

    private boolean doIsCompleteTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node != null) {
                if(node.left == null && node.right != null) {
                    return false;
                }
                queue.offer(node.left);
                queue.offer(node.right);
            }else {
                break;
            }
        }
            while (!queue.isEmpty()) {
                if (queue.poll() != null) {
                    return false;
                }
            }
            return true;
        }
    }



    private void doDfs(TreeNode node,int i) {
        if (node == null) {
            return;
        }
        count++;
        index = Integer.max(index, i);
        doDfs(node.left, 2*i);
        doDfs(node.right, 2*i+1);

    }
}

发表于 2022-11-11 22:07:48 回复(1)

Java

键盘都敲坏了.

BFS广度优先求解

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    public boolean isCompleteTree (TreeNode root) {
       // 如果根为null，就返回true
        if(root == null){
            return true;
        }
        /*
         * 判断不是完全二叉树，有3种情况:
         *      1. 左子节点为空，右子节点不为空
         *      2. 当左子节点不为空，右子节点为空的时候，后面继续迭代当前层时，只要发现还有节点 它就不是完全二叉树
         *      2. 当左子节点不为空，右子节点为空的时候，后面继续迭代下一层时，只要发现还有下一层有节点，它就不是完全二叉树
         */

        // 定义一个链表，用于保存每一层的节点
        LinkedList<TreeNode> linked = new LinkedList<>();

        linked.add(root);  // 先添加根节点

        boolean flag = false; // 定义一个状态码，当出现右子节点为null时，就设置为true

        int size; // 保存循环中每一次链表的长度

        TreeNode treeNode; // 保存每一次取出的链表头节点

        // 链表不为空 循环继续
        while (!linked.isEmpty()){
            // 获取链表长度
            size = linked.size();

            // 根据size 进行循环 依次取出链表头节点
            for (int i = 0; i < size; i++) {
                // 取出头节点
                treeNode = linked.removeFirst();

                // 只要左子节点为空，右子节点不为空  直接返回false
                if(treeNode.left == null && treeNode.right != null) return false;

                // 能执行到这里，只有以下两种情况
                // 1.treeNode.left!=null   (right可能 null || !null)
                // 2.treeNode.left ==null  treeNode.right==null

                // 只要左子节点有值 就添加链表
                if(treeNode.left !=null){
                    // 如果flag为真，表示在这之前的层级或者当前层级中 已经出现了right为空的情况，
                    // 既然已经出现过right为空的情况  那么此if代码块还能进入，已经不是完全二叉树了。就返回false
                    // 首次执行到这，flag一定为false
                    if(flag) return false;
                    // 链表添加节点
                    linked.add(treeNode.left);
                }
                // right!=null 链表添加节点
                if(treeNode.right != null)linked.add(treeNode.right);
                // right为空，flag设置为true
                else flag = true;

            }
        }
        // 循环结束，表示该树符合完全二叉树，返回true
        return true;
    }
}

发表于 2022-11-06 12:26:53 回复(0)

Java

牛客用户007

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    public boolean isCompleteTree (TreeNode root) {
        // write code here
        if (root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        boolean tag = false;
        while (!queue.isEmpty()) {
            TreeNode temp = queue.poll();
            if (temp == null) {
                tag = true;
                continue;
            }
            if (tag) {
                return false;
            }
            queue.add(temp.left);
            queue.add(temp.right);
        }
        return true;
    }
}

发表于 2022-09-12 15:03:05 回复(0)

Java

624huiguorou

判断是不是完全二叉树

区别是：完全二叉树在层序遍历中最后出现null后，一直是null。而非完全二叉树则是在层序遍历中出现null后，后面还出现非null节点。

所以直接层序遍历，这个特殊，由于需要判断null，所以要加null到queue里。

当poll出来为null时，需要continue。如果是完全二叉树，则一直continue到结束。

如果是非完全二叉树，则会poll出来非null，这里最好记录一个boolean变量，表示是否到达节点尾，从而当null后面出现非null节点时直接返回false。

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    public boolean isCompleteTree (TreeNode root) {
        // write code here
        //层序遍历，在队列里加null。完全二叉树当poll出null时，后面应该都是null
        //非完全二叉树，poll出一个null后，后面还有非null元素
        
        //层序遍历，需要加null进去判断（通常不用加null）
        if(root == null) return true;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean isLast = false;
        while(!queue.isEmpty()){
            TreeNode t = queue.poll();
            //如果是完全二叉树，t应该一直为null，直到结束
            if(t == null){
                isLast = true;
                continue;
            }
            //非完全二叉树，出现null后又出现非null元素
            if(isLast){
                return false;
            }
            //加入的是t的左节点和右节点
            queue.offer(t.left);
            queue.offer(t.right);
        }
        return true;
    } 
}

发表于 2022-07-25 16:53:21 回复(3)

判断是不是完全二叉树

输入

输出

输入

输出

输入

输出

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题