完全二叉树判定实战：GESP六级真题BFS与DFS双解法解析

作为衡量编程能力的权威认证之一，CCF的GESP考试在六级阶段着重考察对数据结构与算法的深入理解和应用。二叉树，尤其是完全二叉树的判定，是其中经久不衰的经典考点。下面这道真题不仅能够检验你的基础知识是否扎实，更能区分不同解题思路下的效率差异，非常具有代表性。

真题需求分析

题目要求很明确：给定一棵包含 n 个节点的有根二叉树（节点编号从 1 到 n，根节点为 1），每个节点都对应一棵以它为根的子树。我们需要计算所有 n 棵子树中，有多少棵是完全二叉树。

最直接的思路是：枚举每个节点作为子树根，然后验证其对应的子树结构是否符合完全二叉树的定义。一种直观的方法是使用层序遍历（BFS）进行暴力验证；更高效的思路则是自底向上（后序遍历）地为每个节点维护状态信息（如深度、是否为满二叉树、是否为完全二叉树），通过子树状态推导当前根节点的状态。

核心概念辨析：避免踩坑

很多同学在此类题目上失分，根本原因在于混淆了“完全二叉树”和“满二叉树”的概念。理解两者的区别是解题的前提：

• 满二叉树：除了叶子节点外，每个节点都有两个子节点，并且所有叶子节点都在同一层。它是一种“完美”形态。
• 完全二叉树：除最后一层外，其余层都是满的，并且最后一层的节点都尽可能地向左聚集。满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。

简单说，完全二叉树更贴近我们实际使用（如堆结构）时的形态，允许最后一层不完全填满，但必须从左到右连续排列。

两种解法深度对比：从暴力到高效

下面结合具体代码，对比分析两种主流的解题思路。它们分别适用于不同的场景，从理解基础到追求性能，你可以根据自己的需求选择。

解法一：BFS层序遍历（直观暴力）

核心逻辑：以每个节点为根，进行一次 BFS（广度优先搜索）层序遍历。在遍历过程中，严格检查节点是否按照完全二叉树“从左到右，连续排列”的规则出现。

判定规则（关键）：
在 BFS 队列遍历过程中，一旦遇到一个空节点（编号为 0），就启动一个“清空”操作：将队列中紧随其后所有连续的空节点全部弹出。完成清空后，如果队列变空了，说明空节点之后再也没有非空节点，这符合完全二叉树的定义；如果队列还不为空，则意味着空节点的后面出现了非空节点，破坏了连续性，因此不是完全二叉树。

思路优势：

• 逻辑直观：模拟了完全二叉树的层序构建过程，易于理解和实现。
• 代码简单：不需要复杂的状态记录和递归，适合刚接触树结构判定的初学者快速上手。

  #include<bits/stdc++.h>
  #define ll long long
  using namespace std;
  const int N=1e5+5;
  //节点结构体 
  struct node{
  int left,right;//左右孩子id 
  }t[N]; 
  int n,cnt;
  //判断当前节点作为根节点的子树是否为完全二叉树 
  bool isOk(int id){
  queue<int> q;
  //1.起点入队
  q.push(id);
  while(!q.empty()){
    int cur=q.front();//取出队首
    //遇到空节点--清空连续的空节点 
    if(cur==0){
      while(!q.empty()&&q.front()==0) q.pop();
      break;
    } 
    q.pop();
    q.push(t[cur].left);
    q.push(t[cur].right); 
  }
  return q.empty();
  } 
  int main(){//3.主函数
  //输入 
  cin>>n;
  for(int i=1;i<=n;i++) cin>>t[i].left>>t[i].right;
  //暴力枚举判断子树
  for(int i=1;i<=n;i++){
      if(isOk(i)) cnt++; 
  } 
  //输出
  cout<<cnt; 
  return 0;
  }

解法二：后序遍历 + 状态回溯（高效最优）

核心逻辑：采用后序遍历（DFS）的方式，自底向上地为每个节点计算三个关键状态，然后利用左右子树的状态来推导当前根节点子树的状态。时间复杂度为 O(n)，能够完美处理 n 高达 1e5 的大数据场景，是解决此类算法/数据结构问题的经典优化思路。

每个节点需要维护的三个信息：

1. deep：当前子树的最大深度（约定空树深度为 0）。
2. full：当前子树是否是满二叉树。
3. comp：当前子树是否是完全二叉树。

核心状态转移公式（必须掌握）：

• 满二叉树判定：当前节点满 = 左子树满 && 右子树满 && 左子树深度 == 右子树深度。
• 完全二叉树判定（两种合法情况，满足其一即可）：
  1. 左右子树深度相同，且左子树是满二叉树，右子树是完全二叉树。
  2. 左子树深度比右子树深度大 1，且左子树是完全二叉树，右子树是满二叉树。

思路优势：

• 效率极高：每个节点仅被访问一次，避免了解法一中对每个子树根节点都进行完整 BFS 的重复计算。
• 结构清晰：通过递归自然地实现了树形DFS/BFS中的后序遍历逻辑，状态定义和转移具有很好的数学美感。

#include<iostream>//1.头文件
using namespace std;//2.命名空间
const int N=1e5+5;
//二叉树节点
struct node{
    int left,right;//左右子节点编号
    int deep;//子树深度 
    bool full,comp;//满 完全 状态 
}t[N];
//后序遍历更新节点
void dfs(int root){
    if(!root) return ;//空树 出口
    //获取左右子节点编号 
    int left=t[root].left,right=t[root].right;
    dfs(left);//递归左子树
    dfs(right);//递归右子树
    //根节点信息回溯更新
    //深度 
    t[root].deep=max(t[left].deep,t[right].deep)+1;
    //满否
    t[root].full=t[left].full&&t[right].full&&(t[left].deep==t[right].deep);
    //完全否
    t[root].comp=t[left].full&&t[right].comp&&(t[left].deep==t[right].deep)||t[left].comp&&t[right].full&&(t[left].deep==t[right].deep+1); 
} 
int main(){//3.主函数
    ios::sync_with_stdio(0);//取消cin和cout的绑定
    cin.tie(0);//给cin加速

    int n;
    cin>>n;
    //输入建树
    for(int i=1;i<=n;i++) cin>>t[i].left>>t[i].right;
    //初始化空树
    t[0].deep=0,t[0].full=t[0].comp=1;//空树为特殊满树 
    //后序遍历更新节点深度 满 完全 状态
    dfs(1);
    //统计结果
    int ans=0;
    for(int i=1;i<=n;i++) ans+=t[i].comp;//完全子树个数
    cout<<ans;

    return 0;
}

考点总结与备考建议

这道 GESP 六级真题精准地命中了“完全二叉树的判定”这一核心算法/数据结构考点，并且巧妙地结合了“树的遍历”进行优化。

备考核心要点：

1. 优先掌握高效算法：当题目数据规模较大（例如 n ≥ 1e5）时，务必使用时间复杂度为 O(n) 的后序遍历解法。暴力 BFS 枚举法可能在部分测试点上超时。
2. 牢记状态推导公式：完全二叉树的两种合法构成情况（左满右完全且同高，或左完全右满且左高右低一）是解题的钥匙，理解并熟记它们能让你在考场上迅速构建出状态转移逻辑。

完全二叉树作为基础且重要的数据结构，其应用非常广泛，例如在堆（优先队列）、内存池管理等场景中。吃透这道题的原理，不仅有助于通过 GESP 认证，更能为你后续学习更复杂的树形算法打下坚实的基础。

对于编程和算法学习中的具体问题，欢迎在云栈社区与其他开发者交流探讨，共同进步。