洛谷：https://www.luogu.com.cn/problem/P15801

不得不说这题出六级确实有点难了

一、问题分析+解题思路推导

1. 明确问题目标

需要统计一棵有根二叉树中，所有以每个节点为根的子树里，属于完全二叉树的数量。核心是要找到一种高效的方式，逐个判断每个子树是否符合完全二叉树的定义。

2. 拆解完全二叉树的判断条件

首先回归完全二叉树的本质特征：

• 完全二叉树的结构可拆解为 “满二叉树的扩展”，因此先定义满二叉树作为辅助判断条件（满二叉树是特殊的完全二叉树）；
• 对于任意节点 u 的子树，要成为完全二叉树，仅存在两种合法结构：
  ① 左子树是满二叉树，右子树是完全二叉树，且左右子树高度相等（最后一层节点在左子树已满，右子树补充且不越界）；
  如下图：
  
  ② 左子树是完全二叉树，右子树是满二叉树，且左子树高度比右子树大 1（最后一层仅在左子树，右子树为满且高度少一层）。
  如下图：
  

3. 确定递归的核心思路

二叉树的子树判断天然适合后序递归（先判断子树，再判断父树），原因是：父节点的子树是否为完全二叉树，完全依赖于左右子树的属性。

因此规划递归需要的核心信息（每个节点需记录的属性）：

• 子树高度（h）：判断左右子树的高度关系；
• 是否为满二叉树（f）：作为完全二叉树判断的辅助条件；
• 是否为完全二叉树（c）：最终需要统计的结果；
• 子树节点数（sz）：本题中实际未直接用于判断，但属于子树的基础属性（代码中保留是因为满二叉树可通过节点数验证，如高度 h 的满二叉树节点数为 2^h-1）。

4. 规划递归流程

1. 边界处理：空节点（编号 0）是递归的终止条件，空树既是满二叉树也是完全二叉树，因此其高度和节点数为 0，满 / 完全标记为真。
2. 递归遍历：对当前节点的左、右子树依次递归，获取子树的所有属性（h、f、c、sz）。
3. 计算当前节点属性：
   • 子树节点数 = 左子树节点数 + 右子树节点数 + 1（当前节点）；
   • 子树高度 = 左右子树高度的最大值 + 1（当前层）；
   • 满二叉树判断：左右子树都是满二叉树 + 左右子树高度相等；
   • 完全二叉树判断：满足上述两种合法结构之一。
4. 统计结果：每判断一个节点的子树是完全二叉树，就将计数器加 1。

二、代码

1. 变量设计（匹配思路中的核心属性）

根据思路中需要记录的属性，定义全局数组（避免递归传参的复杂度，且 1e5 规模的数组在全局区可正常分配）：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;  // 匹配题目n≤1e5的规模

// 核心变量：对应思路中的属性
int cnt=0;           // 统计完全二叉树子树数量（思路中的计数器）
int l[N],r[N];       // 存储每个节点的左右儿子（输入数据）
int sz[N],h[N];      // sz：子树节点数，h：子树高度
bool c[N],f[N];      // c：是否为完全二叉树，f：是否为满二叉树

2. 递归函数实现（匹配思路中的递归流程）

void dfs(int u)
{
    // 步骤1：边界处理（空节点），匹配思路中的边界条件
    if(u==0)
    {
        sz[u]=h[u]=0;
        c[u]=f[u]=1;  // 空树是满/完全二叉树
        return;
    }
    
    // 步骤2：递归处理左右子树，匹配思路中的“先子后父”
    dfs(l[u]);
    dfs(r[u]);
    
    // 步骤3：计算当前节点的基础属性（节点数、高度）
    sz[u]=sz[l[u]]+sz[r[u]]+1;  // 思路中“子树节点数计算规则”
    h[u]=max(h[l[u]],h[r[u]])+1;  // 思路中“子树高度计算规则”
    
    // 步骤4：判断满二叉树，匹配思路中的满二叉树条件
    f[u]=(f[l[u]] && f[r[u]] && h[l[u]]==h[r[u]]);
    
    // 步骤5：判断完全二叉树，匹配思路中的两种合法结构
    c[u]=(f[l[u]] && c[r[u]] && h[l[u]]==h[r[u]])  // 结构①
         || (c[l[u]] && f[r[u]] && h[l[u]]==h[r[u]]+1);  // 结构②
    
    // 步骤6：统计结果，匹配思路中的“计数器累加”
    if (c[u]) cnt++;
}

3. 主函数实现（匹配思路中的整体执行流程）

int main()
{
    int n;
    cin>>n;
    // 输入：读取每个节点的左右儿子，匹配思路中的“输入环节”
    for (int i=1;i<=n;i++) cin>>l[i]>>r[i];
    // 执行：从根节点递归，匹配思路中的“递归执行”
    dfs(1);
    // 输出：统计结果，匹配思路中的“输出环节”
    cout<<cnt;
    return 0;
}

最后附上AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int cnt=0;
int l[N],r[N];
int sz[N],h[N];
bool c[N],f[N];
void dfs(int u)
{
    if(u==0)
    {
        sz[u]=h[u]=0;
        c[u]=f[u]=1;
        return;
    }
    dfs(l[u]);
    dfs(r[u]);
    sz[u]=sz[l[u]]+sz[r[u]]+1;
    h[u]=max(h[l[u]],h[r[u]])+1;
    f[u]=(f[l[u]] && f[r[u]] && h[l[u]]==h[r[u]]);
    c[u]=(f[l[u]] && c[r[u]] && h[l[u]]==h[r[u]]) || (c[l[u]] && f[r[u]] && h[l[u]]==h[r[u]]+1);
    if (c[u]) cnt++;
}
int main()
{
    int n;
    cin>>n;
    for (int i=1;i<=n;i++) cin>>l[i]>>r[i];
    dfs(1);
    cout<<cnt;
    return 0;
}

记录： https://www.luogu.com.cn/record/268441384

三、思路到代码的核心映射总结

解题思路阶段	核心逻辑	代码落地方式
问题拆解	完全二叉树的两种合法结构	用c[u]的逻辑表达式实现两种结构的 “或” 判断
递归规划	后序遍历，先子后父	dfs函数中先递归左、右子树，再计算当前节点属性
辅助条件	满二叉树作为判断依据	定义f[u]，通过左右子树的f和高度相等判断
结果统计	逐个节点判断并计数	定义cnt，每次c[u]=true时cnt++
执行流程	输入→递归→输出	主函数中读取输入、调用dfs(1)、输出cnt

四、关键补充

1. 为什么选择后序递归？因为父节点的所有属性（高度、满 / 完全标记）都依赖子节点的结果，后序遍历能保证计算父节点时，子节点的属性已确定。
2. 时间复杂度为 O (n)，符合题目 n≤1e5 的效率要求。