1、定义：

一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。

如果对满二叉树的结点进行编号, 约定编号从根结点起, 自上而下, 自左而右。则深度为k的, 有n个结点的二叉树, 当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时, 称之为完全二叉树。

完全二叉树

2、分析

根据完全二叉树的特点，我们可以推断出两点：

1. 如果某个结点有右孩子没有左孩子，那么这棵树不是完全二叉树；

2. 如果某个结点的左右孩子不双全，那么按照层次遍历的顺序该结点之后的所有结点都是叶结点；

3、代码实现

public static class Node {
    public int value;
    public Node left;
    public Node right;

    public Node(int data) {
        this.value = data;
    }
}

//判断是否为完全二叉树
public static boolean isCBT(Node head) {
    if (head == null) {
        return true;
    }
    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;
        //System.out.print(head.value + " ");
        if (
            //如果已经遇到左右孩子不双全结点，又遇到了不是叶结点的结点
            (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;
}