还是题目传送门
这题说实话，雀食很难。（我才不会告诉你我想了1个多小时）我认(kan)真(le)思(ti)考(jie)才知道这题要用DFS传输3个数据：是否为完全二叉树、是否为满二叉树、深度。
Solution
要知道这颗子树是否为完全二叉树，要判断这几个条件：
当自己的两颗子树深度相同时
1.当右子树为满二叉树且左子树也为满二叉树
2.当右子树为满二叉树且左子树为完全二叉树当自己的两颗子树深度差为1时（且左子树较深）
1.当左子树为满二叉树且右子树也为满二叉树
2.当左子树为满二叉树且右子树为完全二叉树
如果不满足上述条件，则该子树不为完全二叉树，否则，该子树则为完全二叉树（第一种情况也为满二叉树）。
注意点
1.空树不仅是完全二叉树，也是满二叉树，只是深度为0。
2.要特判一下叶子节点。
AC Code
#include<bits/stdc++.h>
using namespace std;
int n, ans = 0;
struct node{int lc;int rc;
}a[100020];
struct tj{int h;bool w;bool m;
};
tj sc(int d){if(a[d].lc == 0 && a[d].rc == 0){ans++;return {1, 1, 1};} tj c1, c2;if(a[d].lc != 0){c1 = sc(a[d].lc);} else {c1 = {0, 1, 1};}if(a[d].rc != 0){c2 = sc(a[d].rc);} else {c2 = {0, 1, 1};}if(c1.h == c2.h){if(c1.m){if(c2.w){if(c2.m){ans++;return {c1.h + 1,1,1};}else{ans++;return {c1.h + 1,1,0};}}else{return {c1.h + 1,0,0};}} else {return {c1.h + 1,0,0};}}else if(c1.h - 1 == c2.h){if(c2.m){if(c1.w){if(c1.m){ans++;return {c1.h + 1, 1, 0};} else {ans++;return {c1.h + 1, 1, 0};}} else {return {c1.h + 1, 0, 0};}} else {return {c1.h + 1, 0, 0};}} else {return {max(c1.h, c2.h) + 1, 0, 0};}
}
int main(){cin >> n;for(int i = 1; i <= n; i++)cin >> a[i].lc >> a[i].rc;sc(1);cout << ans;return 0;
}
总结
本题比较难想，富有逻辑，需要仔细思考。