[数据结构与算法] 算法-判断是否是完全二叉树

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 算法-判断是否是完全二叉树 -> 正文阅读

[数据结构与算法]算法-判断是否是完全二叉树

定义：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。

public static boolean CBT(Node head){
        if (head != null){
            //新建一个队列
            LinkedList<Node> queue = new LinkedList<>();
            //判断是否是叶子节点
            boolean leaf = false;
            Node l = null;
            Node r = null;
            queue.add(head);
            while (!queue.isEmpty()){
                head = queue.poll();
                l = head.left;
                r = head.right;
                if (    //当此节点为叶子节点且左树或右树不为空是false
                        (leaf && (l != null || r != null)) ||
                                //右节点不为空且左节点为空
                                (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;
    }