第 65 题
二叉树按二叉链表形式存储，试编写一个判别给定二叉树是否为完全二叉树的算法。
[tag_link]
参考答案
层序扫描时把左右空指针也入队。一旦遇到第一个空位置，后续队列中若再出现非空结点，就说明层序编号出现空洞，该树不是完全二叉树。
伪代码
IsComplete(T):
if T == null: return true
Q.enqueue(T); seenNull = false
while not Q.empty():
p = Q.dequeue()
if p == null:
seenNull = true
else:
if seenNull: return false
Q.enqueue(p.left) // 空指针也入队
Q.enqueue(p.right)
return true
复杂度
每个真实结点及其边界空指针至多处理一次，时间 O(n)，队列空间 O(n)，通常记为 O(w)。
边界条件
空树通常视为完全二叉树；单结点树成立；只有左孩子成立，只有右孩子不成立。
易错点
只把非空孩子入队会丢失空位信息，从而把“右边仍有结点”的非法结构误判为完全。
评分要点
采用层序；空指针入队；首空后拒绝非空；覆盖空树和单侧孩子。