二叉树：判断其是否为一个完全满二叉树

一、 什么是完全二叉树

1.1 定义

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

1.2 完全二叉树判定

1. 使用中序遍历二叉树，生成一个LinkedList集合队列
2. 每次弹出一个节点，根据该节点获取左右子树节点
3. 如果左数为空，右树不为空，其不是一个完全二叉树
4. 如果遇到了不双全的节点之后，又发现当前节点不是叶节点，其不是一个完全二叉树

二、源码

  public static boolean isCB1(Node head) {
        if (head == null) {
            return true;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(head);
        boolean flag = false;
        while (!queue.isEmpty()) {
            head = queue.poll();
            Node left = head.left;
            Node right = head.right;
            if (
                    (flag && (left != null || right != null)) || (left == null && right != null)
            ) {
            }
            if (left != null) {
                queue.add(left);
            }
            if (right != null) {
                queue.add(right);
            }
            if (left == null || right == null) {
                flag = true;
            }
        }
        return flag;
    }