很多同学第一次看到这题时会有一种感觉：
树 子树 完全二叉树 统计个数感觉特别难。
实际上，这道题是典型的：
树形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、样例1：
1 ├──2 │ └──4 └──3答案：
42、为什么？
（1）结点4：
4完全二叉树
✔
（2）结点3：
3完全二叉树
✔
（3）结点2：
2 / 4完全二叉树
✔
（4）结点1：
1 / \ 2 3 / 4也是完全二叉树
✔
（5）总共：
4棵四、暴力枚举能做吗？
1、有的同学第一想法：
枚举每个结点 判断一次2、如果：
n=1000003、每次判断都遍历整棵子树。
复杂度：
O(n²)会超时。
4、所以必须：
DFS + 树形DP
五、什么是树形DP？
1、我们学过很多DP。
（1）例如：
爬楼梯
dp[i]表示：
走到第i级台阶的方法数（2）转移：
dp[i] = dp[i-1] + dp[i-2]（3）这里：
状态在一条线上移动：
1 ↓ 2 ↓ 3 ↓ 4（4）所以叫：
线性DP2、但是树不一样。
（1）例如：
1 / \ 2 3 / \ 4 5（2）结点1有两个孩子：
2 3（3）不是一条线。
而是一棵树。
（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) 于是还需要 mx：
mx[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）是不是很像线性DP？
dp[i] = ...（4）只是：
这里的状态来自：
左儿子 右儿子而不是：
i-1 i-2（5）这就是树形DP。
十二、如何判断完全二叉树？
这是整题核心。
1、先记一个关键结论：
对于完全二叉树：
左边永远不会比右边更空（1）例如允许：
A / B（2）不允许：
A \ B（3）因为完全二叉树一定：
从左往右填（4）所以：
左子树必须比右子树更饱满。
（5）代码体现：
mn[left] >= mx[right]2、第二个条件：
高度差不能超过1例如：
（1）允许：
高度3 高度2（2）不允许：
高度5 高度2（3）代码：
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
树形状态统计
都会轻松很多，因为它们本质上都是：
先解决孩子 再解决自己这一个核心思想。
