奇偶树 (Even-Odd Tree)

1. 题目描述

题目背景： 在二叉树的性质校验中，除了基本的结构检查，有时需要根据层级的奇偶性来验证节点值的合法性。这类问题通常出现在对特定数据结构（如某些变种平衡树）的约束检查中。

任务描述： 如果一棵二叉树满足下述条件，则称之为 奇偶树 ：

• 根节点 所在的层下标为 0 ，其子节点所在层下标为 1 ，依此类推。
• 对于每一个 偶数下标 层，所有节点的值都是 奇数 ，且按从左到右的顺序 严格递增 。
• 对于每一个 奇数下标 层，所有节点的值都是 偶数 ，且按从左到右的顺序 严格递减 。

给定一棵拥有 $n$ 个节点的二叉树，请判断该树是否为 奇偶树。

输入格式：

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

输出格式： 如果该树是奇偶树，输出 true，否则输出 false。

样例 1： 输入：

10
1 2 3
10 4 0
4 5 6
3 7 8
7 9 0
9 0 10
12 0 0
8 0 0
6 0 0
2 0 0

输出：

true

样例 2： 输入：

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

输出：

false

样例 3： 输入：

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

输出：

false

2. 预备知识点

1. 层序遍历 (BFS)：由于判定规则完全依赖于“层”，BFS 是最直接的工具。
2. 奇偶性判定：利用 x % 2 != 0 判定奇数，x % 2 == 0 判定偶数。
3. 单调性校验：每一层需要维护一个 prev 变量，用于与当前节点值比较。
4. 二叉树存储：结构体数组（静态建树）。

3. 启发式思维引导

第一步：拆解约束条件

在草稿纸上列出表格，理清每一层的逻辑准则： | 层下标 | 权值要求 | 顺序要求 | prev 初始值建议 | | :--- | :--- | :--- | :--- | | 偶数 (0, 2, 4...) | 必须是 奇数 | 严格递增 | 极小值 (如 0) | | 奇数 (1, 3, 5...) | 必须是 偶数 | 严格递减 | 极大值 (如 1e9) |

第二步：BFS 状态设计

• 使用一个队列 Q，并记录当前层的深度 level。
• 在处理每一层之前，根据 level % 2 决定该层的 prev 初值和判定逻辑。

第三步：复杂度分析

• 时间复杂度：$O(N)$。每个节点访问一次。
• 空间复杂度：$O(N)$。队列在最坏情况下（满二叉树底层）需要存储约 $N/2$ 个节点。
• 优化建议：对于 $N=10^5$ 的数据，建议使用 scanf 或手写快读，避免 cin 带来的 IO 瓶颈。

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

graph TD
    A(开始) --> B(初始化队列 Q 并加入根节点编号 1)
    B --> C(设置 level 为 0)
    C --> D{Q 是否为空}
    
    D -- 是 --> E(输出 true)
    E --> End(结束)
    
    D -- 否 --> F(获取当前层大小 sz)
    F --> G{level 是否为偶数}
    
    G -- 是 --> H1(设置 prev 为极小值)
    G -- 否 --> H2(设置 prev 为极大值)
    
    H1 --> I(循环 sz 次)
    H2 --> I
    
    I -- 迭代中 --> J(弹出队首节点 u)
    J --> K{level 为偶数 吗}
    
    K -- 是 --> L1{u 的值是偶数 或者 u 的值小于等于 prev 吗}
    K -- 否 --> L2{u 的值是奇数 或者 u 的值大于等于 prev 吗}
    
    L1 -- 是 --> M(输出 false 并结束)
    L2 -- 是 --> M
    
    L1 -- 否 --> N(将 u 的左右子节点入队 并 更新 prev 为 u 的值)
    L2 -- 否 --> N
    
    N --> I
    I -- 循环结束 --> O(level 增加 1)
    O --> D

5. 读题关键词总结

在 NOI 竞赛中，遇到树论题目要关注以下关键词：

1. “层下标” (Level Index)：
   • 明确是从 0 开始还是从 1 开始。本题从 0 开始。
2. “严格” (Strictly)：
   • 意味着不能相等。递增必须是 val > prev，递减必须是 val < prev。
3. “奇偶性交叉”：
   • 层下标的奇偶与权值的奇偶往往是相反的或相关的，读题时要在草稿纸上标注清楚，防止代码逻辑写反。
4. $N \le 10^5$：
   • 空间上，数组大小要开够；时间上，要考虑 $O(N)$ 算法。

教练点评： 这道题是“层序遍历”与“条件约束”的结合。最容易出错的地方在于 层号奇偶性与权值奇偶性的对应关系，以及 单调性的初值设置（偶数层递增，初值设极小；奇数层递减，初值设极大）。考场上建议写完代码后，用样例 2 这种反例手动模拟一遍逻辑。加油！