首页 > 试题广场 >

判断是不是完全二叉树

[编程题]判断是不是完全二叉树
  • 热度指数：64362 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个二叉树，确定他是否是一个完全二叉树。

完全二叉树的定义：若二叉树的深度为 h，除第 h 层外，其它各层的结点数都达到最大个数，第 h 层所有的叶子结点都连续集中在最左边，这就是完全二叉树。（第 h 层可能包含 [1~2h] 个节点）

数据范围：节点数满足
样例图1：
样例图2：
样例图3：

示例1

输入

{1,2,3,4,5,6}

输出

true
示例2

输入

{1,2,3,4,5,6,7}

输出

true
示例3

输入

{1,2,3,4,5,#,6}

输出

false

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
Java
bb1701头像 bb1701 
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头像 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头像 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头像 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头像 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头像 牛客用户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头像 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)
Java
牛客873067774号头像 牛客873067774号
思路：检查树的层序遍历（null值也放入队列中），检查null之后是否还有非空的节点；若有，则是非完全二叉树； 
/*
 * 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) {
        return isCompleteTree_levelOrder(root);
    }
    
    private boolean isCompleteTree_levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        
        queue.offer(root);
        
        boolean flagFirstNull = false;
        while (!queue.isEmpty()) {
            TreeNode pNode = queue.poll();
            
            if (pNode == null) {
                flagFirstNull = true;
                continue;
            }
            
            if (flagFirstNull == true) return false; 
            queue.offer(pNode.left);
            queue.offer(pNode.right);
        }

        return true;
    }
}


发表于 2022-07-23 18:35:26 回复(0)
Java
lizi-hust头像 lizi-hust
Java 深度优先搜索 
public class Solution {
    private int count = 0, index = 0;
    public boolean isCompleteTree (TreeNode root) {
        dfs(root, 1);
        return count==index;
    }
    public void dfs(TreeNode root, int i){
        if(root==null) return;
        count++;
        index = Math.max(index, i);
        dfs(root.left, 2*i);
        dfs(root.right, 2*i+1);
    }
}


发表于 2022-07-17 23:54:49 回复(0)
Java
FARO_Z头像 FARO_Z

在 BSF 时，我们习惯在将子节点加入队列时，进行非空判断
但是对于 "完全二叉树" 这道题，我们恰恰需要保留这些空节点
从而借此判断二叉树的完整性

import java.util.*;


public class Solution {

    public boolean isCompleteTree (TreeNode root) {
        if (root==null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean hasNull = false;
        while (!queue.isEmpty()) {
            TreeNode tmp = queue.poll();
            if (tmp==null) {
                hasNull=true;
                continue;
            }
            if (hasNull) return false;
            queue.offer(tmp.left);
            queue.offer(tmp.right);
        }
        return true;
    }
}
发表于 2022-07-14 17:36:03 回复(0)
Java
牛客839384289号头像 牛客839384289号 
    public boolean isCompleteTree (TreeNode root) {
        // write code here
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node==null){
                if(queue.peek()!=null){
                    return false;
                }
            }else{
                queue.add(node.left);
                queue.add(node.right);
            }
        }
        return true;
    }

发表于 2022-06-02 16:49:06 回复(0)
提交观点

问题信息

树 dfs 广度优先搜索(BFS)
难度：
33条回答 3532浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号