一、 什么是完全二叉树
1.1 定义
一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
1.2 完全二叉树判定
- 使用中序遍历二叉树，生成一个LinkedList集合队列
- 每次弹出一个节点，根据该节点获取左右子树节点
- 如果左数为空，右树不为空，其不是一个完全二叉树
- 如果遇到了不双全的节点之后，又发现当前节点不是叶节点，其不是一个完全二叉树
二、源码
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;
}
