完全二叉树 题解

题目分析

本题给出一棵以 $1$ 为根的二叉树，共有 $n$ 个结点。要求统计出在这棵树的所有子树中，有多少棵是完全二叉树。

完全二叉树的定义：除最后一层外，其余各层都是满的，并且最后一层的结点都靠左排列。根据这个性质，可以推导出一些关于结点深度的条件，从而在 DFS 的过程中判断子树是否为完全二叉树。

我们需要高效地计算答案，结点数最大可达 $10^5$，因此算法复杂度需要接近 $O(n)$。

解题思路

对于一棵二叉树，若它是完全二叉树，则其左右子树也必然是完全二叉树，并且满足下面两个关于结点深度的条件。

我们定义深度：从当前结点出发到达某个叶子结点所经过的结点数（包含自身）。空结点深度记为 $0$。

在 DFS 后序遍历时，维护每个结点 $u$ 的以下信息：

• $mn[u]$：以 $u$ 为根的子树中，从 $u$ 到任意叶子的最短深度。
• $mx[u]$：以 $u$ 为根的子树中，从 $u$ 到任意叶子的最长深度。
• $chk[u]$：标记以 $u$ 为根的子树是否是完全二叉树（$1$ 表示是，$0$ 表示否）。

根据完全二叉树“左满右不满、最后一层靠左”的特性，可以得出判定条件：

1. 左子树的叶子结点不能比右子树的叶子结点“浅”
   即左子树的最短深度应不小于右子树的最长深度：
   

   $$mn[l_u]\ge mx[r_u]$$
   
   这保证了右子树不会伸得比左子树的任何叶子还要深，满足“靠左”的约束。

2. 整棵子树深度差不超过 1
   即最短深度与最长深度之差为 $0$ 或 $1$：
   

   $$mn[u]\ge mx[u]-1$$
   
   这保证了除最后一层外，上层都是满的。

同时，空结点被视为完全二叉树（$chk[0] = 1$），深度为 $0$。

只要在递归返回时依照这些规则合并左右子树的信息，便能判断每个子树是否是完全二叉树，并累加答案。

算法说明

1. 读入 $n$，存储每个结点的左右儿子 $l_i, r_i$。
2. 从根结点 $1$ 开始进行 DFS（后序遍历）：
   • 若当前结点为 $0$（空结点），直接返回。
   • 先递归处理左子树和右子树。
   • 计算当前结点的最短深度和最长深度：
     
     $$mn[u]=1+\min (mn[l_u],mn[r_u])$$
     
     
     $$mx[u]=1+\max (mx[l_u],mx[r_u])$$
   • 判断是否完全二叉树：初始 $chk[u] = 1$，然后与左右子树的 $chk$ 值进行 & 运算（保证子树都是完全二叉树），再与两个深度条件进行 & 运算。
   • 若满足所有条件，ans 加一。
3. 输出答案 ans。

由于空结点在访问时会被设置为 $chk[0]=1$，而深度 $mn[0]=mx[0]=0$（全局数组默认为 $0$），因此叶子结点（左右儿子均为 $0$）能够被正确判定为完全二叉树。

时间复杂度分析

每个结点只会被访问一次，递归操作均为 $O(1)$，因此总时间复杂度为 $O(n)$。
空间上使用了几个长度为 $n$ 的数组，复杂度为 $O(n)$，完全满足 $n \le 10^5$ 的限制。

参考代码

cpp
复制
1#include <cstdio>
2#include <algorithm>
3using namespace std;
4
5const int N = 1e5 + 5;
6int n;
7int l[N], r[N];          // 左右儿子
8int mn[N], mx[N];        // 最短深度、最长深度
9int chk[N];              // 是否是完全二叉树
10int ans;
11
12void dfs(int u) {
13    chk[u] = 1;          // 先假设当前子树是完全二叉树
14    if (!u) return;      // 空结点直接返回，chk[0]=1, mn[0]=mx[0]=0
15
16    dfs(l[u]);
17    dfs(r[u]);
18
19    // 左右子树必须都是完全二叉树
20    chk[u] &= chk[l[u]] & chk[r[u]];
21
22    // 计算当前子树的最短深度和最长深度
23    mn[u] = 1 + min(mn[l[u]], mn[r[u]]);
24    mx[u] = 1 + max(mx[l[u]], mx[r[u]]);
25
26    // 条件1：左子树的最短深度 >= 右子树的最长深度
27    chk[u] &= mn[l[u]] >= mx[r[u]];
28    // 条件2：当前子树深度差不超过1
29    chk[u] &= mn[u] >= mx[u] - 1;
30
31    ans += chk[u];       // 满足所有条件则计入答案
32}
33
34int main() {
35    scanf("%d", &n);
36    for (int i = 1; i <= n; i++)
37        scanf("%d%d", &l[i], &r[i]);
38
39    dfs(1);
40    printf("%d\n", ans);
41    return 0;
42}

代码解释

• chk[u] = 1 放在函数开头，即使 $u=0$ 也会执行，将空结点标记为“完全二叉树”。
• dfs(l[u]) 和 dfs(r[u]) 先递归处理左右儿子，获取它们的深度信息和完全二叉树标记。
• &= 运算将条件逐一叠加：子树必须是完全二叉树，且深度满足两个约束。
• 变量 ans 在每次判断完后累加 chk[u]，最后输出即可。

通过以上判定规则和后序遍历，我们能在线性时间内求出所有完全二叉子树的个数。