[GESP202606 六级] 满二叉树

视频讲解：[GESP202606 六级] 满二叉树-信息学奥赛GESP等级考试真题解析

一、原题

题目描述

给定一棵包含 n 个结点的有根二叉树，结点依次以 1,2,…,n 编号，根结点编号为 1。

对于结点 i，其左儿子的编号记为 li​，右儿子编号记为 ri​。特别地，如果左儿子不存在则 li​=0，如果右儿子不存在则 ri​=0。

树中每个结点都对应一棵以其为根的子树。请你求出给定有根树的所有 n 棵子树中，有多少棵子树是满二叉树。

满二叉树是指所有叶子深度均相同，且除叶子外均有两个儿子的二叉树，例如以下三棵二叉树均是满二叉树：

() () ()
/ \\ / \\
() () () ()
/ \\ / \\
() ()() ()

在上面这棵有 3 个节点的二叉树中，有 3 个子树是满二叉树（包括整个树本身，及所有的单个叶子节点）；

又例如，

(1)
/ \\
(2) (3)
/ \\
(4) (5)

在上面这棵有 5 个节点的二叉树中，有 4 个子树是满二叉树（包括节点 3 的子树，以及所有单个叶子节点）。

输入格式

第一行，一个正整数 n，表示有根二叉树结点数量。

接下来 n 行，每行两个非负整数 li​,ri​，表示结点 i 的左儿子编号和右儿子编号，整数之间以空格分隔。

输出格式

输出一行，一个整数，表示所有子树中满二叉树的数量。

输入输出样例

输入 #1

4
2 3
4 0
0 0
0 0

输出 #1

23

输入 #2

3
2 3
0 0
0 0

输出 #2

3

说明/提示

数据范围

对于 40% 的测试点，保证 1≤n≤500。

对于所有测试点，保证 1≤n≤10^5。

二、做题思路

1)二维数组构造二叉树

#include<bits/stdc++.h>
using namespace std;
int tree[100005][2];
int main(){
//1)二维数组构造二叉树
//1.1)确定结点数量n
int n;cin>>n;
//1.2)填充每个结点左右子树
for(int i=1;i<=n;i++)
cin>>tree[i][0]>>tree[i][1];
}

2)深搜每一个结点

#include<bits/stdc++.h>
using namespace std;
int tree[100005][2];
void dfs(int x){
//2.2)子树不为空，就向下搜索
if(tree[x][0]!=0) dfs(tree[x][0]);
if(tree[x][1]!=0) dfs(tree[x][1]);
}
int main(){
//1)二维数组构造二叉树
//…
//2)深搜每一个结点
//2.1)深搜函数，从1开始
dfs(1);
}

3)判断是否为满二叉树

3.1)叶子节点是满二叉 ，高度为1

#include<bits/stdc++.h>
using namespace std;
int tree[100005][2];
int d[100005];
bool m[100005];
void dfs(int x){
//3)判断是否为满二叉树
//3.1)叶子节点是满二叉 ，高度为1
if(!tree[x][0]&&!tree[x][1]){//左右为空是叶子节点
m[x]=d[x]=1;
return ;
}
//2.2)子树不为空，就向下搜索
//…
}
int main(){
//1)二维数组构造二叉树
//…
//2)深搜每一个结点
//2.1)深搜函数，从1开始
dfs(1);
}

3.2)满二叉条件：左右高度相同，左右都是满二叉

#include<bits/stdc++.h>
using namespace std;
int tree[100005][2];
int d[100005];
bool m[100005];
void dfs(int x){
//3)判断是否为满二叉树
//3.1)叶子节点是满二叉 ，高度为1
//…
//2.2)子树不为空，就向下搜索
//…
//3.2)满二叉条件：左右高度相同，左右都是满二叉
if(d[tree[x][0]]==d[tree[x][1]]&&m[tree[x][0]]&&m[tree[x][1]]){
m[x]=1;
d[x]=max(d[tree[x][0]],d[tree[x][1]])+1;
}
}
int main(){
//1)二维数组构造二叉树
//…
//2)深搜每一个结点
//2.1)深搜函数，从1开始
dfs(1);
}

4)计算满二叉数量

#include<bits/stdc++.h>
using namespace std;
int tree[100005][2];
int d[100005];
bool m[100005];
void dfs(int x){
//3)判断是否为满二叉树
//3.1)叶子节点是满二叉 ，高度为1
//…
//2.2)子树不为空，就向下搜索
//…
//3.2)满二叉条件：左右高度相同，左右都是满二叉
//…
}
int main(){
//1)二维数组构造二叉树
//…
//2)深搜每一个结点
//2.1)深搜函数，从1开始
dfs(1);
//4)计算满二叉数量
int ans=0;
for(int i=1;i<=n;i++) if(m[i]) ans++;
cout<<ans;
}

三、答案

#include<bits/stdc++.h>
using namespace std;
int tree[100005][2];
int d[100005];
bool m[100005];
void dfs(int x){
//3)判断是否为满二叉树
//3.1)叶子节点是满二叉 ，高度为1
if(!tree[x][0]&&!tree[x][1]){//左右为空是叶子节点
m[x]=d[x]=1;
return ;
}
//2.2)子树不为空，就向下搜索
if(tree[x][0]!=0) dfs(tree[x][0]);
if(tree[x][1]!=0) dfs(tree[x][1]);
//3.2)满二叉条件：左右高度相同，左右都是满二叉
if(d[tree[x][0]]==d[tree[x][1]]&&m[tree[x][0]]&&m[tree[x][1]]){
m[x]=1;
d[x]=max(d[tree[x][0]],d[tree[x][1]])+1;
}
}
int main(){
//1)二维数组构造二叉树
//1.1)确定结点数量n
int n;cin>>n;
//1.2)填充每个结点左右子树
for(int i=1;i<=n;i++)
cin>>tree[i][0]>>tree[i][1];
//2)深搜每一个结点
//2.1)深搜函数，从1开始
dfs(1);
//4)计算满二叉数量
int ans=0;
for(int i=1;i<=n;i++) if(m[i]) ans++;
cout<<ans;
}