视频讲解：[GESP202603 六级] 完全二叉树-信息学奥赛GESP等级考试真题解析
一、原题
题目描述
给定一棵包含 n 个结点的有根二叉树，结点依次以 1,2,…,n 编号，根结点编号为 1。
对于结点 i，其左儿子的编号记为 li，右儿子编号记为 ri。特别地，如果左儿子不存在则 li=0，如果右儿子不存在则 ri=0。
树中每个结点都对应一棵以其为根的子树。请你求出给定有根树的所有 n 棵子树中，有多少棵子树是完全二叉树。
输入格式
第一行，一个正整数 n，表示有根二叉树结点数量。
接下来 n 行，每行两个正整数 li,ri，表示结点 i 的左儿子编号和右儿子编号。
输出格式
输出一行，一个整数，表示所有子树中完全二叉树的数量。
输入输出样例
输入 #1
4 2 3 4 0 0 0 0 0输出 #1
4输入 #2
4 2 3 0 0 4 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],w[100005]; void dfs(int x){ //3)判断是否为完全二叉树 //3.1)叶子节点，是完全二叉，是满二叉，高度为1 if(!tree[x][0]&&!tree[x][1]){//左右为空是叶子节点 w[x]=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],w[100005]; void dfs(int x){ //3)判断是否为完全二叉树 //3.1)叶子节点，是完全二叉，是满二叉，高度为1 //... //2.2)子树不为空，就向下搜索 //... //3.2)计算高度 (左右取大的+1) d[x]=max(d[tree[x][0]],d[tree[x][1]])+1; } int main(){ //1)二维数组构造二叉树 //... //2)深搜每一个结点 //2.1)深搜函数，从1开始 dfs(1); }3.3)判断满二叉
#include<bits/stdc++.h> using namespace std; int tree[100005][2]; int d[100005]; bool m[100005],w[100005]; void dfs(int x){ //3)判断是否为完全二叉树 //3.1)叶子节点，是完全二叉，是满二叉，高度为1 //... //2.2)子树不为空，就向下搜索 //... //3.2)计算高度 (左右取大的+1) //... //3.3)判断满二叉：左右高度相同，左右都是满二叉 if(d[tree[x][0]]==d[tree[x][1]]&&m[tree[x][0]]&&m[tree[x][1]]) m[x]=1; } int main(){ //1)二维数组构造二叉树 //... //2)深搜每一个结点 //2.1)深搜函数，从1开始 dfs(1); }3.4)判断完全二叉的2种情况
#include<bits/stdc++.h> using namespace std; int tree[100005][2]; int d[100005]; bool m[100005],w[100005]; void dfs(int x){ //3)判断是否为完全二叉树 //3.1)叶子节点，是完全二叉，是满二叉，高度为1 //... //2.2)子树不为空，就向下搜索 //... //3.2)计算高度 (左右取大的+1) //... //3.3)判断满二叉：左右高度相同，左右都是满二叉 //... //3.4)判断完全二叉的2种情况 //左右高度相同：左满 且 右完全 if(d[tree[x][0]]==d[tree[x][1]]) if(m[tree[x][0]]&&w[tree[x][1]]) w[x]=1; //左高度==右高度+1：左完全 且 右满或空 if(d[tree[x][0]]==d[tree[x][1]]+1) if(w[tree[x][0]]&&(m[tree[x][1]]||!tree[x][1])) w[x]=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],w[100005]; void dfs(int x){ //3)判断是否为完全二叉树 //3.1)叶子节点，是完全二叉，是满二叉，高度为1 //... //2.2)子树不为空，就向下搜索 //... //3.2)计算高度 (左右取大的+1) //... //3.3)判断满二叉：左右高度相同，左右都是满二叉 //... //3.4)判断完全二叉的2种情况 //左右高度相同：左满 且 右完全 //.. } int main(){ //1)二维数组构造二叉树 //... //2)深搜每一个结点 //2.1)深搜函数，从1开始 dfs(1); //4)计算完全二叉数量 int ans=0; for(int i=1;i<=n;i++) if(w[i]) ans++; cout<<ans; }三、答案
#include<bits/stdc++.h> using namespace std; int tree[100005][2]; int d[100005]; bool m[100005],w[100005]; void dfs(int x){ //3)判断是否为完全二叉树 //3.1)叶子节点，是完全二叉，是满二叉，高度为1 if(!tree[x][0]&&!tree[x][1]){//左右为空是叶子节点 w[x]=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)计算高度 d[x]=max(d[tree[x][0]],d[tree[x][1]])+1; //3.3)判断满二叉：左右高度相同，左右都是满二叉 if(d[tree[x][0]]==d[tree[x][1]]&&m[tree[x][0]]&&m[tree[x][1]]) m[x]=1; //3.4)判断完全二叉的2种情况 //左右高度相同：左满 且 右完全 if(d[tree[x][0]]==d[tree[x][1]]) if(m[tree[x][0]]&&w[tree[x][1]]) w[x]=1; //左高度==右高度+1：左完全 且 右满或空 if(d[tree[x][0]]==d[tree[x][1]]+1) if(w[tree[x][0]]&&(m[tree[x][1]]||!tree[x][1])) w[x]=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(w[i]) ans++; cout<<ans; }
