根据深度计算

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n;
int l[N],r[N];
int mind[N],maxd[N],check[N];
int ans;
void dfs(int u)
{
	check[u]=1;
	if(!u) return ;//空的
	dfs(l[u]),dfs(r[u]); //递归计算左右子树的完全树和高度
	check[u]&=check[l[u]]&&check[r[u]];
	mind[u]=1+min(mind[l[u]],mind[r[u]]);
	maxd[u]=1+max(maxd[l[u]],maxd[r[u]]);
	check[u]&=mind[l[u]]>=maxd[r[u]];//左子树的最小高度大于等于右子树的最大高度,保证右子树是满的
	check[u]&=mind[u]>=maxd[u]-1;//高度之差为一层，保证最多只有一层是空的
	ans+=check[u];
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>l[i]>>r[i];
	}
	dfs(1);
	cout<<ans;
	return 0;
}

bfs搜索每层

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int l[N],r[N];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>l[i]>>r[i];
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		queue<int> q;
		q.push(i);
		bool ok=true;
		int cnt=0; //缺失的数字
		while(q.size()&&ok)
		{
			int u=q.front();
			q.pop();
			if(l[u]==0) //有缺失
			{
				cnt++;
			}
			else
			{
				q.push(l[u]); //入队
				if(cnt) //前面有缺失了
				{
					ok=false;
				}
			}
			if(r[u]==0)
			{
				cnt++;
			}
			else
			{
				q.push(r[u]); //入队
				if(cnt) //前面有缺失了
				{
					ok=false;
				}
			}
		}
		if(ok) ans++; //整个遍历完了都没有缺失的
	}
	cout<<ans;
	return 0;
}