Meta 判断完全二叉树：层序第一个空位之后

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 完全二叉树除最后一层外全部填满，最后层节点尽量靠左；空树训练定义True。节点左右缺失以None表示。

解题路线

1. 层序队列从root开始，真实节点把left/right按顺序入队，包括None。遇第一个None设置gap；之后遇任何真实节点就False。
2. 层序对应完整树的数组位置顺序。完全树真实节点必须占据连续前缀，第一个空之后不能再有真实节点，恰好就是gap规则。
3. 不能只判断每节点没有右无左：较左子树先缺位但较右子树仍有孩子，也会不完整，局部规则看不出来。
4. 同样不能等同满二叉树或每个节点两孩子。完全树允许最末一个父只有左孩子；平衡高度差也不保证节点靠左。
5. 入队空位数量与真实节点成比例，不递归扩展None的children，因此不会枚举无限完整树位置。

手动走一遍

根1，左2、右3，2只有左4而3无孩子：层序[1,2,3,4,None,None,None]合法。若2缺右而3还有左5，空位后出现5，非法；只有root.right无left立即非法。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from collections import deque


def is_complete(root):
    """Empty tree complete. Once level-order sees None, later real node is invalid."""
    queue=deque([root]);gap=False
    while queue:
        node=queue.popleft()
        if node is None:gap=True
        else:
            if gap:return False
            queue.append(node.left);queue.append(node.right)
    return True

复杂度

O(N)时间、O(width)队列，最坏O(N)空间。独立oracle可给根编号1、左右2i/2i+1，N节点完全当且仅当maxIndex=N，但深树编号会增长，BFSgap无需大整数索引。

易错点与追问

容易失分的边界

• 遇None立即返回True会漏后面非空节点。
• 只检右无左遗漏跨父节点的洞。

继续深挖

• 若保证输入完全，如何O(log²N)数节点？这是利用既定性质的另一问题，不能用于验证之前。
• 把空树定义False只需入口合同变化，测试应固定一致。