检查二叉树的完全性 (Check Completeness of a Binary Tree)

1. 题目描述

题目背景： 完全二叉树（Complete Binary Tree）是堆排序（Heap Sort）等高级算法的基础结构。在 NOI 竞赛中，判定一个给定的存储结构是否符合完全二叉树的定义是考察树论基础的经典题型。

定义回顾： 若设二叉树的深度为 $h$，除第 $h$ 层外，其它各层 ($1 \sim h-1$) 的结点数都达到最大个数，第 $h$ 层所有的结点都连续集中在最左边，这就是完全二叉树。（注：第 $h$ 层可以有 $1 \sim 2^{h-1}$ 个节点）。

任务描述： 给定一棵拥有 $n$ 个节点的二叉树，节点编号从 $1$ 到 $n$。判断这棵树是否是完全二叉树。

输入格式：

1. 第一行包含一个整数 $n$ ($1 \le n \le 100$)，表示节点总数。
2. 接下来的 $n$ 行，每行包含三个整数 $v_i, l_i, r_i$。
   • $v_i$ 为第 $i$ 个节点的权值。
   • $l_i$ 为左孩子编号。
   • $r_i$ 为右孩子编号。
3. 如果孩子不存在，则编号为 $0$。根节点固定为编号 $1$。

输出格式： 如果该树是完全二叉树，输出 true，否则输出 false。

样例 1： 输入：

6
1 2 3
2 4 5
3 6 0
4 0 0
5 0 0
6 0 0

输出：

true

(解释：每一层都是满的，最后一层的节点 6 紧靠左侧)

样例 2： 输入：

6
1 2 3
2 4 5
3 0 7
4 0 0
5 0 0
7 0 0

输出：

false

(解释：节点 7 位于第 3 层的右侧，但它的左边（节点 3 的左孩子）出现了空缺)

2. 预备知识点

1. 二叉树的层序遍历 (BFS)：这是判定完全性的核心工具。
2. 完全二叉树的性质：在层序遍历序列中，一旦出现了一个“空节点”，那么序列中后续的所有位置都必须是“空节点”。
3. 节点索引性质（可选）：若根节点索引为 1，节点 $i$ 的左孩子为 $2i$，右孩子为 $2i+1$。在完全二叉树中，所有节点的索引最大值恰好等于节点数 $n$。

3. 启发式思维引导

第一步：视觉模拟

在草稿纸上画出一个完全二叉树。尝试进行层序遍历（按层从左往右）。

• 思考：如果你在遍历过程中遇到了第一个“空位置”（即某个节点没有左孩子或没有右孩子），后面还能再出现非空的节点吗？
• 结论：如果出现了“空”之后又看到了“实”的节点，那就说明中间有断层，不符合完全性。

第二步：BFS 状态设计

我们需要在传统的 BFS 基础上增加一个“标记位”：

1. 使用一个队列存储节点。
2. 初始化 foundEmpty = false。
3. 遍历时：
   • 如果当前节点不为空：
     • 如果 foundEmpty 已经是 true 了，说明之前见过空位，现在又见到节点，直接判定 false。
     • 将左右孩子（包括空孩子）依次入队。
   • 如果当前节点为空：
     • 标记 foundEmpty = true。

第三步：复杂度与边界思考

• 时间复杂度：$O(n)$。每个节点进出队列一次。
• 空间复杂度：$O(n)$。队列最宽处。
• 优化建议：由于 $n$ 很小（只有 100），甚至可以用数组索引法判定，但层序遍历法在 $n=10^5$ 时依然是最稳健的。

4. 算法流程图 (C++14 逻辑)

为了兼容 Mermaid 语法，流程图中使用中文描述逻辑。

graph TD
    A(开始) --> B(初始化队列 Q)
    B --> C(将根节点 1 入队)
    C --> D(初始化 reachedEnd 标记为 假)
    
    D --> E{队列是否为空}
    E -- 是 --> F(输出 true)
    F --> G(结束)
    
    E -- 否 --> H(弹出队首节点 u)
    H --> I{u 是否等于 0}
    
    I -- 是 --> J(设置 reachedEnd 为 真)
    J --> E
    
    I -- 否 --> K{reachedEnd 是否为 真}
    K -- 是 --> L(输出 false)
    L --> G
    
    K -- 否 --> M(将 u 的左孩子入队)
    M --> N(将 u 的右孩子入队)
    N --> E

5. 读题关键词总结

在 NOI 读题时，看到以下关键词要提高警惕：

1. “完全二叉树” (Complete Binary Tree)：

   • 直觉转换：层序遍历不能有“断层”。
   • 备选方案：节点编号最大值是否等于节点数（注意大范围下索引可能超过 long long）。

2. “连续集中在左边” (As far left as possible)：

   • 指示：遍历顺序必须严格按照先左后右。

3. 数据范围 $n \le 100$：

   • 暗示：这题不需要复杂的空间优化，重点在于逻辑的严密性。

4. “节点编号从 1 到 n”：

   • 坑点：注意题目给出的输入是否一定是连通的（本题固定根为 1，简化了逻辑）。如果没固定根，可能需要先找入度为 0 的点。

教练点评： 这道题是 BFS 的变种应用。普通 BFS 只处理非空节点，而判定完全二叉树的 BFS 必须处理空节点。一旦空节点出现在非空节点之前，判定失败。这是理解层序遍历性质的极佳练习。