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

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

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;
    }