[GESP202603 六级] 完全二叉树

视频讲解[GESP202603 六级] 完全二叉树-信息学奥赛GESP等级考试真题解析一、原题题目描述给定一棵包含 n 个结点的有根二叉树结点依次以 1,2,…,n 编号根结点编号为 1。对于结点 i其左儿子的编号记为 li​右儿子编号记为 ri​。特别地如果左儿子不存在则 li​0如果右儿子不存在则 ri​0。树中每个结点都对应一棵以其为根的子树。请你求出给定有根树的所有 n 棵子树中有多少棵子树是完全二叉树。输入格式第一行一个正整数 n表示有根二叉树结点数量。接下来 n 行每行两个正整数 li​,ri​表示结点 i 的左儿子编号和右儿子编号。输出格式输出一行一个整数表示所有子树中完全二叉树的数量。输入输出样例输入 #14 2 3 4 0 0 0 0 0输出 #14输入 #24 2 3 0 0 4 0 0 0输出 #23说明/提示对于 40% 的测试点保证 1≤n≤500。对于所有测试点保证 1≤n≤10^5。二、做题思路1)二维数组构造二叉树#includebits/stdc.h using namespace std; int tree[100005][2]; int main(){ //1)二维数组构造二叉树 //1.1)确定结点数量n int n;cinn; //1.2)填充每个结点左右子树 for(int i1;in;i) cintree[i][0]tree[i][1]; }2)深搜每一个结点#includebits/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#includebits/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)计算高度#includebits/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)判断满二叉#includebits/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种情况#includebits/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)计算完全二叉数量#includebits/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 ans0; for(int i1;in;i) if(w[i]) ans; coutans; }三、答案#includebits/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;cinn; //1.2)填充每个结点左右子树 for(int i1;in;i) cintree[i][0]tree[i][1]; //2)深搜每一个结点 //2.1)深搜函数从1开始 dfs(1); //4)计算完全二叉数量 int ans0; for(int i1;in;i) if(w[i]) ans; coutans; }