题解 | A106105.完全二叉树

---

思路

首先你看到这道题，一定知道，这道题要用 $\text{dfs}$（深度优先搜索） 做。如不明白 $\text{dfs}$，请移步至这里（OI Wiki $\text{dfs}$）。

问题来了：怎么 $\text{dfs}$？

首先，我们要先明确完全二叉树的性质。完全二叉树只有最下面两层结点的度数可以小于 $2$，且最下面一层的结点都集中在该层最左边的连续位置上。

那么，我们可以基于性质，试着推演一下它的规律。

• 如图，我们可以发现，这棵完全二叉树左子树为满二叉树，右子树为完全二叉树，且左右子树高相同。故可以推出本题的第一个性质：一棵树左子树为满二叉树，右子树为完全二叉树，左右子树高相同，这棵树即为完全二叉树。你也可以举出更多例子，但是，你会注意到还有一种情况。

• 如图，我们又可发现，这棵完全二叉树左子树为完全二叉树，右子树为满二叉树，且左子树比右子树高 $1$。故可以推出本题的第二个性质：一棵树左子树为完全二叉树，右子树为满二叉树，左子树比右子树高 $1$，这棵树即为完全二叉树。你也可以举出更多例子，不过你会发现，所有完全二叉树要么满足上一条，要么满足这一条（注意满二叉树符合上一种情况）。

所以，你只要想到了上面两种情况，这道题估计就做出来了！

实现

我们使用递归 $\text{dfs}$，从 $1$ 开始先序遍历，每次进行两种判断并继续搜索。

• 定义什么：

int n; //输入的n
int l[N], r[N], f[N], c[N], h[N]; 
//l[i]：i的左儿子 r[i]：i的右儿子 
//f[i],c[i]：i是否为满二叉树（f）、完全二叉树（c）
//h[i]：i的高度
int ans = 0; //记录答案

• 完全二叉树判定：当前项完全二叉树判断分两种情况讨论：

c[key] = ((f[l[key]] && c[r[key]] && (h[l[key]] == h[r[key]]))/*第一种情况，左子树满右完全，高相等*/ || (c[l[key]] && f[r[key]] && (h[l[key]] - 1 == h[r[key]])) /*第二种*/);

• 满二叉树判定：如果左右子树都是满二叉树且高相等，也很好理解。

f[key] = (f[l[key]] && f[r[key]] && h[l[key]] == h[r[key]]);

• 终止条件：当前最尾层。

if (!key){
	f[key] = 1; //初始化
	c[key] = 1;
	return ;
}

• 高的累加：左右子树最高的 $+1$。

h[key] = max (h[l[key]], h[r[key]]) + 1;

代码（有注释）

#include <bits/stdc++.h>
#define int long long 
#define rds pair<int, int>

using namespace std;

const int N = 1e5 + 5;
int n; //输入的n
int l[N], r[N], f[N], c[N], h[N]; 
//l[i]：i的左儿子 r[i]：i的右儿子 
//f[i],c[i]：i是否为满二叉树（f）、完全二叉树（c）
//h[i]：i的高度
int ans = 0; //记录答案

void dfs(int key){ //dfs函数，key为当前节点
	if (!key){ //终止条件
		f[key] = 1; //初始化完全二叉树、满二叉树，因为一个元素就是完全二叉树、满二叉树
		c[key] = 1;
		return ; //直接退出
	}
	dfs(l[key]); //左子树
	dfs(r[key]); //右子树
	h[key] = max (h[l[key]], h[r[key]]) + 1; //左子树、右子树最高的高度+1
	f[key] = (f[l[key]] && f[r[key]] && h[l[key]] == h[r[key]]); //满二叉树：左右子树都是满二叉树且高相等
	c[key] = ((f[l[key]] && c[r[key]] && (h[l[key]] == h[r[key]]))/*第一种情况，左子树满右完全，高相等*/ || (c[l[key]] && f[r[key]] && (h[l[key]] - 1 == h[r[key]])) /*第二种*/); //完全二叉树判定
	if (c[key]) ans++ ; //是完全二叉树，累加答案
}
signed main(){
	cin >> n; //输入
	for (int i = 1; i <= n; i++){ //左右子树输入
		cin >> l[i] >> r[i];
	}
	dfs(1); //从根开始遍历
	cout << ans << endl; //输出答案
	return 0;
} 

代码（有注释）

#include <bits/stdc++.h>
#define int long long 
#define rds pair<int, int>

using namespace std;

const int N = 1e5 + 5;
int n;
int l[N], r[N], f[N], c[N], h[N]; 
int ans = 0; 

void dfs(int key){
	if (!key){ 
		f[key] = 1; 
		c[key] = 1;
		return ; 
	}
	dfs(l[key]); 
	dfs(r[key]); 
	h[key] = max (h[l[key]], h[r[key]]) + 1; 
	f[key] = (f[l[key]] && f[r[key]] && h[l[key]] == h[r[key]]); 
	c[key] = ((f[l[key]] && c[r[key]] && (h[l[key]] == h[r[key]])) || (c[l[key]] && f[r[key]] && (h[l[key]] - 1 == h[r[key]])) ); 
	if (c[key]) ans++ ;
}
signed main(){
	cin >> n; 
	for (int i = 1; i <= n; i++){ 
		cin >> l[i] >> r[i];
	}
	dfs(1);
	cout << ans << endl; 
	return 0;
}