二叉树的深度-层序遍历法

【描述】给定一棵二叉树， 要求用层序遍历的方式求该二叉树的深度。
二叉树深度的定义： 从根结点到最远叶结点依次经过的结点个数（含根、叶结点）。
【输入描述】第一行是一个整数 n， 表示二叉树的结点个数。 二叉树结点编号从 1到 n， 根结点为 1， n <= 10 。接下来有 n 行， 依次对应二叉树的 n 个结点。 每行有两个整数， 分别表示该结点的左儿子和右儿子的结点编号。 如果第一个（第二个） 数为-1 则表示没有左（右） 儿子。
【输出描述】输出一个整型数， 表示树的深度。
【输入样例】
3
2 3
-1 -1
-1 -1
【输出样例】
2
【输入样例】
7
2 7
3 6
4 5
-1 -1
-1 -1
-1 -1
-1 -1
【输出样例】
4

#include<iostream>#include<queue>usingnamespacestd;structtree_node{intls,rs;//ls:左孩子结点编号，rs：右孩子结点编号intdepth;//深度};tree_node tree[11];queue<int>q;// 为了节约空间，队列中只保存树的编号intn;intans;//深度最大值voidbfs(){// 根结点编号1，入队tree[1].depth=1;q.push(1);while(!q.empty()){intid=q.front();q.pop();intdepth=tree[id].depth;ans=max(ans,depth);//更新深度最大值// 先左后右，子结点（编号）入队if(tree[id].ls!=-1){tree[tree[id].ls].depth=depth+1;//设置左子节点的深度q.push(tree[id].ls);}if(tree[id].rs!=-1){tree[tree[id].rs].depth=depth+1;//设置右子节点的深度q.push(tree[id].rs);}}}intmain(){// 读入和保存树cin>>n;for(inti=1;i<=n;i++)cin>>tree[i].ls>>tree[i].rs;// 从根结点开始层序遍历bfs();// 输出cout<<ans<<endl;return0;}/* 本题测试点 【样例输入1】 1 -1 -1 【样例输出1】 1 【样例输入2】 7 2 3 4 5 6 7 -1 -1 -1 -1 -1 -1 -1 -1 【样例输出2】 3 【样例输入3】 4 2 -1 3 -1 4 -1 -1 -1 【样例输出3】 4 【样例输入4】 6 2 3 4 5 -1 -1 6 -1 -1 -1 -1 -1 【样例输出4】 4 【样例输入5】 4 -1 2 -1 3 -1 4 -1 -1 【样例输出5】 4 */

GESP202406 六级第二题 【二叉树】

【描述】
小杨有一棵包含几个节点的二叉树，且根节点的编号为1。这棵二叉树任意一个节点要么是白色，要么是黑色。之后小杨会对这棵二叉树进行q次操作，每次小杨会选择一个节点，将以这个节点为根的子树内所有节点的颜色反转,即黑色变成白色，白色变成黑色。
小杨想知道q次操作全部完成之后每个节点的颜色。
【输入描述】
第一行一个正整数n，表示二叉树的节点数量。第二行n-1个正整数，第i(1<i<n-1)个数表示编号为i+1的节点的父亲节点编号，数据保证是一棵二叉树。
第三行一个长度为n的01串，从左到右第i(1≤i<n)位如果为0，表示编号为i的节点颜色为白色，否则为黑色。
第四行一个正整数q，表示操作次数。
接下来q行每行一个正整数 a_i(1<a_i≤n)，表示第i次操作选择的节点编号。
【输出描述】
输出一行一个长度为n的 01串，表示q次操作全部完成之后每个节点的颜色。从左到右第i(1<i≤n)位如果为
0，表示编号为i的节点颜色为白色，否则为黑色。
【输入样例】
6
3 1 1 3 4
100101
3
1
3
2
【输出样例】
010000

#include<iostream>usingnamespacestd;#defineLEN100000structtree_node{intson[2];//子结点编号intvalue;};tree_node tree[LEN];intn,times;chartmp[LEN];//操作：以rootid为根的所有结点值翻转voidprocess(introotid){if(rootid==0)return;//空节点不处理tree[rootid].value=1-tree[rootid].value;//0->1,1->0process(tree[rootid].son[0]);process(tree[rootid].son[1]);}intmain(){// 读入和保存树cin>>n;for(inti=1;i<=n-1;i++){intid;cin>>id;if(tree[id].son[0]==0)tree[id].son[0]=i+1;elsetree[id].son[1]=i+1;}cin>>tmp;for(inti=0;i<n;i++){tree[i+1].value=tmp[i]-'0';}cin>>times;//操作次数for(inti=1;i<=times;i++){intid;cin>>id;process(id);}//输出for(inti=1;i<=n;i++){cout<<tree[i].value;}return0;}/* 本题测试点 【样例输入1】 6 3 1 1 3 4 100101 3 1 3 2 【样例输出1】 010000 【样例输入2】 4 1 2 3 0000 3 1 2 1 【样例输出2】 0111 【样例输入3】 7 1 1 2 2 3 3 1111111 2 2 3 【样例输出3】 1000000 【样例输入4】 1 0 2 1 1 【样例输出4】 0 */

二叉树的宽度

【描述】给定一棵二叉树， 求该二叉树的宽度。
二叉树宽度的定义： 是指具有节点数目最多的那一层的节点个数，即所有层中节点数的最大值。
【输入描述】第一行是一个整数 n， 表示二叉树的结点个数。 二叉树结点编号从 1到 n， 根结点为 1， n <= 10 。接下来有 n 行， 依次对应二叉树的 n 个结点。
每行有两个整数， 分别表示该结点的左儿子和右儿子的结点编号。 如果第一个（第二个） 数为-1 则表示没有左（右）儿子。
【输出描述】输出一个整型数， 表示树的宽度。
【输入样例】
3
2 3
-1 -1
-1 -1
【输出样例】
2
【输入样例】
7
2 7
3 6
4 5
-1 -1
-1 -1
-1 -1
-1 -1
【输出样例】
2
【提示】使用队列逐层遍历，统计每层节点数，最大值就是树的宽度。

#include<iostream>#include<queue>usingnamespacestd;structtree_node{intls,rs;//ls:左孩子结点编号，rs：右孩子结点编号intdepth;//深度 即层号};tree_node tree[11];queue<int>q;// 为了节约空间，队列中只保存树的编号intn;intwidth[11];// 层宽度数组，第i层宽度width[i]voidbfs(){// 根结点编号1，入队tree[1].depth=1;//根节点在第1层q.push(1);while(!q.empty()){intid=q.front();q.pop();//按层统计宽度intdepth=tree[id].depth;width[depth]++;// 先左后右，非空子结点（编号）入队if(tree[id].ls!=-1){tree[tree[id].ls].depth=depth+1;//设置左子节点的深度q.push(tree[id].ls);}if(tree[id].rs!=-1){tree[tree[id].rs].depth=depth+1;//设置右子节点的深度q.push(tree[id].rs);}}}intmain(){// 读入和保存树cin>>n;for(inti=1;i<=n;i++)cin>>tree[i].ls>>tree[i].rs;// 从根结点开始层序遍历bfs();// 找到宽度最大值并输出intmax_width=0;for(inti=1;i<=n;i++)max_width=max(max_width,width[i]);cout<<max_width<<endl;return0;}/* 本题测试点 【样例输入1】 1 -1 -1 【样例输出1】 1 【样例输入2】 7 2 3 4 5 6 7 -1 -1 -1 -1 -1 -1 -1 -1 【样例输出2】 4 【样例输入3】 4 2 -1 3 -1 4 -1 -1 -1 【样例输出3】 1 【样例输入4】 4 -1 2 -1 3 -1 4 -1 -1 【样例输出4】 1 【样例输入5】 6 2 3 4 5 6 -1 -1 -1 -1 -1 -1 -1 【样例输出5】 3 */

二叉树的权值

【描述】给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从上到下、从左到右的顺序依次是 A1,A2,…,AN，如下图所示:
现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点权值之和最大?如果有多个深度的权值和同为最大，请你输出其中最小的深度。
注:根的深度是 1。
【输入描述】
第一行包含一个整数 N。
第二行包含 N 个整数 A1,A2,…,AN。
【输出描述】
输出一个整数代表答案。
【输入样例】
7
1 6 5 4 3 2 1
【输出样例】
2
对于所有评测用例，1≤ N< 10^5,0 <|Ai|< 10^5

【提示】
完全二叉树的第k层有2^k个结点(第一层k=0)，因此可以通过计数的方式，在枚举数组的同时，分别累计每个深度的结点数量。
一旦某一层累加的结点数足够了，就记录并比较大小，然后初始化各个数据，重新再累加计算。

#include<iostream>#include<cmath>usingnamespacestd;intmain(){intn;cin>>n;intcnt=0,k=0,sum=0,ans=0,ans2=0;//cnt计数，k控制每一层是2的几次方个，sum求和，ans1记录最大值，ans2记录深度for(inti=0;i<n;i++){intx;cin>>x;cnt++;sum+=x;if(cnt==pow(2,i)||i==n-1){//计数2^k个，或者累加到了最后一个结点cnt=0;k++;if(sum>ans){ans=sum;ans2=k;}sum=0;}}cout<<ans2<<endl;return0;}/* 本题测试点 【样例输入1】 1 5 【样例输出1】 1 【样例输入2】 2 3 4 【样例输出2】 2 【样例输入3】 3 1 2 3 【样例输出3】 2 【样例输入4】 5 1 1 1 5 5 【样例输出4】 3 【样例输入5】 3 4 5 6 【样例输出5】 2 */