题源链接：洛谷 P17013 [GESP202606 六级] 满二叉树

---

一、背景

在算法竞赛的树形结构专题中，有一类问题特别考验选手对"递归定义"的理解——它们不问你树怎么遍历，而是问你树的某种性质怎么判定。GESP 六级的这道满二叉树题，就是这类问题的典型代表。

题目场景很清晰：给定一棵有根二叉树，要求统计所有子树中有多少棵是满二叉树。满二叉树的定义有两个硬性条件：所有叶子深度相同，且每个非叶子结点都有两个儿子。这两个条件看似简单，但要高效地统计所有子树，就需要一种自底向上的判定策略。

本文就从这道满二叉树题出发，聊聊树形动态规划的核心思想，以及递归定义如何转化为递归算法这个漂亮的对应关系。

---

二、核心思想

2.1 满二叉树的递归定义

拿到这道题，很多选手的第一直觉可能是：对每个子树，判断它是不是满二叉树。但子树的数量是 $O(n)$，如果每个子树都用 $O(n)$ 的时间判断，总复杂度就是 $O(n^2)$，对于 $n=10^5$ 的数据会超时。

关键在于发现满二叉树的递归定义：

一棵二叉树是满二叉树，当且仅当：

1. 它是单个叶子结点；或者
2. 它的左右子树都是满二叉树，且左右子树的高度相同。

这个定义的美妙之处在于：判断一棵子树是否为满二叉树，只需要知道它的左右子树是否为满二叉树，以及左右子树的高度。不需要遍历整棵子树！

我们可以把满二叉树想象成俄罗斯套娃：

• 最内层是一个叶子（高度 $1$）
• 每往外套一层，都需要左右两个同样高的套娃
• 如果左右套娃高度不同，或者其中一个不是套娃，这一层就"套不上"

2.2 自底向上的信息传递

基于递归定义，我们可以设计一种自底向上的判定策略：

• 叶子结点：$flag=true$，$dep=1$，计数 $+1$
• 非叶子结点：先递归处理左右子树，获取 $flag[left]$、$dep[left]$、$flag[right]$、$dep[right]$
  • 如果左右都是满二叉树且高度相同：$flag=true$，$dep=dep[left]+1$，计数 $+1$
  • 否则：$flag=false$，$dep=max(dep[left],dep[right])+1$

这里的 $dep[x]$ 表示以 $x$ 为根的子树中，叶子到 $x$ 的最大距离（即子树高度）。对于满二叉树，所有叶子深度相同，所以高度就是统一的叶子深度。

信息传递的特征：

• 后序遍历：先处理子结点，再处理父结点，确保子问题的信息已准备好
• 状态压缩：每个结点只需维护两个值（$flag$ 和 $dep$），而非整棵子树的结构
• 计数时机：在判定某个结点为满二叉树时立即计数，利用 DFS 遍历所有子树

2.3 为什么高度信息足够？

满二叉树要求"所有叶子深度相同"。如果我们知道左右子树都是满二叉树，且高度相同，那么以当前结点为根的子树中：

• 左子树的所有叶子深度 = $dep[left]$（相对于左子树根）
• 右子树的所有叶子深度 = $dep[right]$（相对于右子树根）
• 当前结点的深度 = $1$
• 所以左子树叶子到当前结点的深度 = $dep[left]+1$
• 右子树叶子到当前结点的深度 = $dep[right]+1$

如果 $dep[left]=dep[right]$，则所有叶子到当前结点的深度都相同（= $dep[left]+1$），满足满二叉树定义。

这就像天平称重：左右两边的"重量"（高度）必须相等，天平才能平衡。如果一边重一边轻，或者一边没有砝码（不是满二叉树），天平就倾斜了。

---

三、算法模板

3.1 算法到底在干什么？——直觉解释

我们的算法是一台"满二叉树检测仪"：

1. 从叶子开始：每个叶子都是满二叉树（高度 $1$），计数 $+1$
2. 逐步向上：对于每个非叶子结点，检查左右子树是否"合格"
3. 合格判定：左右都是满二叉树且高度相同 $
   ightarrow$ 当前也是满二叉树，计数 $+1$
4. 不合格处理：标记为不合格，高度取左右最大值 $+1$
5. 汇总结果：DFS 遍历完所有结点后，$ans$ 就是满二叉树子树的总数

整个过程就像质量检测流水线：从最小的零件（叶子）开始检测，合格的零件组装成更大的部件，再检测部件是否合格，层层向上。

3.2 万能模板 —— 伪代码 + 实战代码

伪代码：

function 统计满二叉树(根结点 root):
    ans = 0
    dfs(root)
    return ans

function dfs(x):
    if x 是叶子:
        flag[x] = true
        dep[x] = 1
        ans += 1
        return

    if 左儿子存在: dfs(左儿子)
    if 右儿子存在: dfs(右儿子)

    if flag[左] 且 flag[右] 且 dep[左] == dep[右]:
        flag[x] = true
        dep[x] = dep[左] + 1
        ans += 1
    else:
        flag[x] = false
        dep[x] = max(dep[左], dep[右]) + 1

实战代码（通用模板）：

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

int n;
int l[N], r[N];
int dep[N];
bool flag[N];
int ans;

void dfs(int x)
{
    if (l[x] == 0 && r[x] == 0)
    {
        flag[x] = true;
        dep[x] = 1;
        ans++;
        return;
    }

    if (l[x] != 0) dfs(l[x]);
    if (r[x] != 0) dfs(r[x]);

    if (flag[l[x]] && flag[r[x]] && dep[l[x]] == dep[r[x]])
    {
        flag[x] = true;
        dep[x] = dep[l[x]] + 1;
        ans++;
    }
    else
    {
        flag[x] = false;
        dep[x] = max(dep[l[x]], dep[r[x]]) + 1;
    }
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> l[i] >> r[i];

    dfs(1);
    cout << ans << endl;
    return 0;
}

3.3 例题实现 —— 本题完整代码

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 100005;              // 常量：最大结点数

int n;                             // n: 二叉树结点数量
int ans;                           // ans: 满二叉树子树的数量
int l[N], r[N];                    // l[i]: 结点 i 的左儿子编号; r[i]: 结点 i 的右儿子编号
int dep[N];                        // dep[i]: 以结点 i 为根的子树高度（叶子深度）
bool flag[N];                      // flag[i]: 以结点 i 为根的子树是否为满二叉树

void dfs(int x)                    // 深度优先搜索，计算以 x 为根的子树信息
{
    if (l[x] == 0 && r[x] == 0)    // 叶子结点：左右儿子都不存在
    {
        flag[x] = true;            // 单个叶子结点是满二叉树
        dep[x] = 1;                // 叶子结点的高度为 1
        ans++;                     // 满二叉树计数加一
        return;
    }

    if (l[x] != 0)                 // 如果左儿子存在
        dfs(l[x]);                 // 递归计算左子树

    if (r[x] != 0)                 // 如果右儿子存在
        dfs(r[x]);                 // 递归计算右子树

    // 判断以 x 为根的子树是否为满二叉树：
    // 条件：左右子树都是满二叉树，且左右子树高度相同
    if (flag[l[x]] == 1 && flag[r[x]] == 1 && dep[l[x]] == dep[r[x]])
    {
        flag[x] = 1;               // 标记为满二叉树
        dep[x] = dep[l[x]] + 1;     // 当前子树高度 = 子树高度 + 1
        ans++;                     // 满二叉树计数加一
    }
    else                            // 不是满二叉树
    {
        flag[x] = 0;               // 标记为非满二叉树
        dep[x] = max(dep[l[x]], dep[r[x]]) + 1;  // 高度取左右子树的最大值
    }
}

signed main()
{
    cin >> n;                      // 读入结点数量

    for (int i = 1; i <= n; i++)  // 读入每个结点的左右儿子编号
    {
        cin >> l[i] >> r[i];
    }

    dfs(1);                        // 从根结点开始 DFS

    cout << ans << endl;           // 输出满二叉树子树的总数

    return 0;
}

3.4 对比实现 —— 其他路径的探讨

本题的核心在于"递归定义转化为递归算法"，但还有其他思路值得了解：

方案	核心思想	时间复杂度	适用场景
DFS + 自底向上（本题做法）	递归定义直接转化	$O(n)$	满二叉树判定，最直观
BFS + 层序遍历	按层检查结点度数	$O(n)$	需要按层处理的其他性质
显式枚举所有子树	对每个结点，遍历其子树判断	$O(n^2)$	仅适用于 $n$ 很小的情况
树链剖分 + 线段树	维护子树信息，支持动态修改	$O(n\log n)$	树结构动态变化时

对于本题，DFS 自底向上是最直接、最高效的方法。BFS 层序遍历也可以做，但需要额外记录每个结点的深度信息，不如 DFS 自然。

3.5 变体清单 —— 常见变形

变体类型	题目描述	关键变化	解法调整
完全二叉树判定	统计完全二叉树子树数量	定义变化	增加结点编号连续性检查
平衡二叉树判定	统计平衡二叉树子树数量	定义变化	条件改为 abs(dep[left] - dep[right]) <= 1
二叉搜索树判定	统计 BST 子树数量	定义变化	增加值域约束，传递 min/max
最大满二叉子树	找最大的满二叉子树	目标变化	记录最大高度/结点数，而非计数
动态修改树结构	支持插入/删除结点	结构动态变化	用 Link-Cut Tree 或欧拉序维护
$k$ 叉树版本	每个结点最多 $k$ 个儿子	度数变化	遍历所有儿子，检查是否都是满 $k$ 叉树且高度相同
带权版本	每个结点有权值，求权值和最大的满二叉子树	增加权值维度	在判定时累加权值，维护最大值

3.6 什么时候不能用？——边界条件和反例

本题的方法依赖于满二叉树的递归定义，一旦定义变化，思路需要调整：

• 只有一个儿子的结点：根据满二叉树定义，非叶子结点必须有两个儿子。如果某个结点只有一个儿子，它及其所有祖先都不可能是满二叉树。
• 空树/空子树：题目保证 $n\ge 1$，但如果需要处理空子树的情况，需要特判。空树可以视为满二叉树（高度 $0$），也可以不视为，取决于题意。
• 高度定义不一致：有些定义中叶子高度为 $0$，有些为 $1$。本题采用叶子高度为 $1$，在代码中需要保持一致。
• 非二叉树：如果是 $k$ 叉树，需要遍历所有儿子，检查是否都是满 $k$ 叉树且高度相同。
• 递归栈溢出：$n=10^5$ 时，递归深度可能达到 $10^5$，在某些环境下可能栈溢出。可以改用显式栈模拟 DFS，或增加编译栈空间。

---

四、底层逻辑

4.1 为什么递归定义能转化为 $O(n)$ 算法？

这是基于树的后序遍历和最优子结构的证明。

设 $flag[x]$ 表示以 $x$ 为根的子树是否为满二叉树，$dep[x]$ 表示以 $x$ 为根的子树高度。

基础情况：如果 $x$ 是叶子（$l[x]=r[x]=0$），则 $flag[x]=true$，$dep[x]=1$。显然成立。

归纳步骤：假设对于 $x$ 的所有后代结点，$flag$ 和 $dep$ 都已正确计算。那么：

• 如果 $flag[l[x]]=true$、$flag[r[x]]=true$ 且 $dep[l[x]]=dep[r[x]]$：

  • 左子树是满二叉树，所有叶子深度相同（= $dep[l[x]]$）
  • 右子树是满二叉树，所有叶子深度相同（= $dep[r[x]]$）
  • 且 $dep[l[x]]=dep[r[x]]$，所以左右子树叶子到 $x$ 的深度都 = $dep[l[x]]+1$
  • 因此以 $x$ 为根的子树是满二叉树，$flag[x]=true$，$dep[x]=dep[l[x]]+1$

• 否则：

  • 要么左右子树不都是满二叉树，要么高度不同
  • 无论哪种情况，以 $x$ 为根的子树不满足满二叉树定义
  • $flag[x]=false$，$dep[x]=\max (dep[l[x]],dep[r[x]])+1$

由数学归纳法，算法正确性得证。每个结点只访问一次，时间复杂度 $O(n)$。

4.2 与经典问题的对比

这道题和经典的树形 DP 问题家族有密切联系：

问题	判定条件	传递信息	时间复杂度
本题：满二叉树	左右都是满二叉树且高度相同	$flag$ + $dep$	$O(n)$
平衡二叉树	abs(dep[left] - dep[right]) <= 1	$flag$ + $dep$	$O(n)$
完全二叉树	层序编号连续 + 叶子在最下层	$size$ + $max\_id$	$O(n)$
二叉搜索树	左 < 根 < 右	$min$ + $max$ + $flag$	$O(n)$
树的最大深度	无	$dep$	$O(n)$
树的直径	无	最长路径长度	$O(n)$

可以看到，树形 DP 的核心在于：为每个结点设计合适的状态，使得父结点的状态可以仅由子结点的状态推导而来。不同的树性质需要不同的状态设计。

4.3 隐含约束的分析

题目中有几个容易被忽略但至关重要的细节：

• 有根二叉树：根结点固定为 $1$，且每个结点最多两个儿子。这保证了树的结构是明确的。
• 结点编号：$1$ 到 $n$ 连续编号，但不一定按层序或先序排列。输入给出的是每个结点的左右儿子编号，可以直接建树。
• $l_i=0$ 或 $r_i=0$ 表示不存在：这是题目约定的空结点表示法，需要用 0 作为哨兵值。
• 子树包含自身：题目要求统计"所有子树"，包括单个结点的子树（叶子）和整棵树本身。DFS 遍历每个结点时自然覆盖了所有子树。

---

五、决策表

面对"树的某种性质判定/统计"类问题，如何根据性质快速选型？

场景特征	推荐方案	时间复杂度	备注
性质可递归定义（如满二叉树）	DFS 后序遍历 + 状态传递	$O(n)$	本题场景，最通用
性质与深度/层次相关	BFS 层序遍历	$O(n)$	如完全二叉树判定
需要支持动态修改	树链剖分 / LCT	$O(\log n)$ 每次	结构变化时
性质涉及路径	两次 DFS 求直径	$O(n)$	如树的直径、最远点对
性质涉及子树大小	DFS + size 数组	$O(n)$	如重心、子树结点数统计
性质涉及值域约束	DFS + 值域传递	$O(n)$	如 BST 判定

一句话总结：递归定义想后序，层次相关想层序，动态修改想剖分，路径问题想两遍 DFS。

---

六、工程视角

树形 DP 和递归判定的思想在实际工程中有着广泛的应用：

1. 编译器语法树优化：编译器在解析源代码后会生成抽象语法树（AST）。某些优化（如常量折叠、死代码消除）需要判断子树是否满足特定模式（如"满二叉树"式的对称结构）。树形 DP 可以高效地在 AST 上传播这些性质。

2. 文件系统完整性检查：文件系统可以看作一棵树，目录是非叶子结点，文件是叶子。某些完整性检查（如"所有目录必须同时包含子目录和文件"）可以建模为满二叉树性质的判定，通过自底向上的 DFS 高效完成。

3. 组织架构分析：在企业组织架构中，每个管理者（非叶子）需要管理若干下属（子结点）。"满二叉树"式的结构要求可以确保管理层的均衡性。通过树形 DP 可以快速评估组织架构是否满足这种均衡要求。

4. 游戏 AI 的决策树：在棋类游戏的 minimax 决策树中，每个结点代表一个局面，子结点代表可能的走法。评估某个局面是否"平衡"（如双方子力对称）时，可以借鉴满二叉树的判定思路，自底向上传递评估信息。

---

七、小结

本文从一道 GESP 六级真题出发，探讨了树形动态规划与满二叉树的递归判定问题。

核心认知可以总结为：

当树的某种性质具有递归定义时，自底向上的 DFS 后序遍历是最自然的判定方式；每个结点只需维护最小必要的状态信息，就能在 $O(n)$ 时间内完成整棵树的判定与统计。

用公式化的语言概括：

$$\text{满二叉树条件}(x)=\{\begin{array}{ll}\text{true},& \text{if }x\text{ 是叶子}\\ \text{满二叉树}(l[x])\wedge \text{满二叉树}(r[x])\wedge (dep[l[x]]=dep[r[x]]),& \text{otherwise}\end{array}$$

答案为 DFS 遍历过程中满足条件的结点总数。

这道题教会我们的，不仅是如何写递归函数和状态数组，更是一种 “递归定义转化为递归算法” 的思维习惯：在算法竞赛中，很多树的性质问题，其解法就藏在性质的定义里。满二叉树的定义本身就是递归的——“左右子树都是满二叉树且高度相同”——这直接提示了后序遍历的解法。这种"定义即算法"的对应关系，是树形问题中最优雅的解题策略。

---

如果这篇文章对你有帮助，欢迎点赞收藏！有任何问题欢迎在评论区留言交流。