GESP2026年3月认证C++六级真题与解析（编程题2 完全二叉树）

很多同学第一次看到这题时会有一种感觉树 子树 完全二叉树 统计个数感觉特别难。实际上这道题是典型的树形DP DFS我们还是用故事方式来拆解。一、什么是完全二叉树先搞懂题目最重要的概念。1、普通二叉树例如A / \ B C / \ D E这是一棵二叉树。2、完全二叉树例如A / \ B C / \ D E这是完全二叉树。因为每一层从左到右排列 中间没有空洞3、再看A / \ B C / D不是完全二叉树。因为B的位置空了 D跑到后面去了出现了空洞。二、题目到底让我们干什么1、题目给一棵树。然后问每个结点都能作为根 形成一棵子树2、例如1 / \ 2 3共有以1为根 以2为根 以3为根三棵子树。然后统计有多少棵子树是完全二叉树三、样例分析1、样例11 ├──2 │ └──4 └──3答案42、为什么1结点44完全二叉树✔2结点33完全二叉树✔3结点22 / 4完全二叉树✔4结点11 / \ 2 3 / 4也是完全二叉树✔5总共4棵四、暴力枚举能做吗1、有的同学第一想法枚举每个结点 判断一次2、如果n1000003、每次判断都遍历整棵子树。复杂度O(n²)会超时。4、所以必须DFS 树形DP五、什么是树形DP1、我们学过很多DP。1例如爬楼梯dp[i]表示走到第i级台阶的方法数2转移dp[i] dp[i-1] dp[i-2]3这里状态在一条线上移动1 ↓ 2 ↓ 3 ↓ 44所以叫线性DP2、但是树不一样。1例如1 / \ 2 3 / \ 4 52结点1有两个孩子2 33不是一条线。而是一棵树。4所以状态不在线上 状态在树上这就叫树形DP六、树形DP最核心思想1、请记住一句话先算儿子再算爸爸这是所有树形DP的灵魂。2、例如1 / \ 2 3 / \ 4 53、想知道结点1的信息必须先知道结点2的信息 结点3的信息4、而要知道结点2的信息又必须先知道结点4的信息 结点5的信息5、所以顺序一定是4 5 2 3 16、发现了吗这正是后序遍历左 右 根7、所以树形DP DFS后序遍历这是第一记忆点。七、这道题到底让我们求什么1、题目问有多少棵子树 是完全二叉树2、例如1 / \ 2 33、实际上有三棵子树以1为根 以2为根 以3为根4、每个结点都对应一棵子树。5、所以我们要做检查每个结点 看看它的子树 是不是完全二叉树八、DP状态设计1、树形DP最重要的事情定义状态2、我们要判断以u为根的子树 是不是完全二叉树3、那么至少要记录chk[u]1表示u这棵子树 是否合法2于是chk[u]1表示是完全二叉树3如果chk[u]0表示不是完全二叉树这就是第一个DP状态。九、仅有chk够吗不够。1、看这个树A / \ B C2、要判断A是否合法。(1) 必须知道左边多高 右边多高(2) 于是还需要 mxmx[u]表示以u为根 最长高度3、例如A / B / C高度3十、为什么还要mn最短高度1、考虑A / B / C有的叶子近。有的叶子远。2、于是记录mn[u]表示最短高度3、这样mx 最长高度 mn 最短高度4、整棵树长什么样。基本就知道了。5、所以本题DP状态chk[u] 以u为根这棵子树是否合法 mx[u] 以u为根最长高度 mn[u] 以u为根最短高度这是第二记忆点。十一、状态转移1、来到结点u。1先递归dfs(left); dfs(right);2于是左子树信息有了 右子树信息有了2、现在开始算自己。计算高度1最长高度mx[u] 1 max(mx[left],mx[right]);2最短高度mn[u] 1 min(mn[left],mn[right]);3是不是很像线性DPdp[i] ...4只是这里的状态来自左儿子 右儿子而不是i-1 i-25这就是树形DP。十二、如何判断完全二叉树这是整题核心。1、先记一个关键结论对于完全二叉树左边永远不会比右边更空1例如允许A / B2不允许A \ B3因为完全二叉树一定从左往右填4所以左子树必须比右子树更饱满。5代码体现mn[left] mx[right]2、第二个条件高度差不能超过1例如1允许高度3 高度22不允许高度5 高度23代码mn[u] mx[u]-13、第三个条件1左右孩子自己也必须合法。chk[left] chk[right]2于是chk[u] 左合法 右合法 左边够满 高度差≤1十三完整DFS流程同学们考试时就记这个流程。1、来到结点u①先算左儿子↓②再算右儿子↓③计算mx↓④计算mn↓⑤判断chk↓⑥统计答案2、流程图u dfs(left) ↓ dfs(right) ↓ 得到左右信息 ↓ 计算mx mn ↓ 判断chk ↓ ans十四参考程序#include cstdio #include algorithm using namespace std; const int N 1e5 5; int n; int l[N], r[N]; int mn[N], mx[N], chk[N]; int ans; void dfs(int u) { chk[u] 1; if (!u) return; dfs(l[u]); dfs(r[u]); chk[u] chk[l[u]] chk[r[u]]; mn[u] 1 min(mn[l[u]], mn[r[u]]); mx[u] 1 max(mx[l[u]], mx[r[u]]); chk[u] mn[l[u]] mx[r[u]]; chk[u] mn[u] mx[u] - 1; ans chk[u]; } int main() { scanf(%d, n); for (int i 1; i n; i) scanf(%d%d, l[i], r[i]); dfs(1); printf(%d\n, ans); return 0; }十五本题总结1、如果让汉克老师用一句话概括这道题不是仅仅判断完全二叉树。而是在考察树形DP的思想。2、树形DP三步①定义状态 ②DFS后序遍历 ③利用左右儿子的状态 计算自己的状态3、本题状态chk[u] mx[u] mn[u]4、本题转移由左右儿子 推出父亲5、这就是树形DP最标准的模型。十五、同学们记忆口诀树形DP并不难 先算孩子再算咱 DFS走后序路 左右信息全拿全 mx最长高度记 mn最短高度算 chk判断合不合法 最后统计答案完我们把这道题真正学懂了那么以后学习树上背包DP树的直径树上最长链换根DP树形状态统计都会轻松很多因为它们本质上都是先解决孩子 再解决自己这一个核心思想。