二叉树的深度-层序遍历法【描述】给定一棵二叉树 要求用层序遍历的方式求该二叉树的深度。二叉树深度的定义 从根结点到最远叶结点依次经过的结点个数含根、叶结点。【输入描述】第一行是一个整数 n 表示二叉树的结点个数。 二叉树结点编号从 1到 n 根结点为 1 n 10 。接下来有 n 行 依次对应二叉树的 n 个结点。 每行有两个整数 分别表示该结点的左儿子和右儿子的结点编号。 如果第一个第二个 数为-1 则表示没有左右 儿子。【输出描述】输出一个整型数 表示树的深度。【输入样例】32 3-1 -1-1 -1【输出样例】2【输入样例】72 73 64 5-1 -1-1 -1-1 -1-1 -1【输出样例】4#includeiostream#includequeueusingnamespacestd;structtree_node{intls,rs;//ls:左孩子结点编号rs右孩子结点编号intdepth;//深度};tree_node tree[11];queueintq;// 为了节约空间队列中只保存树的编号intn;intans;//深度最大值voidbfs(){// 根结点编号1入队tree[1].depth1;q.push(1);while(!q.empty()){intidq.front();q.pop();intdepthtree[id].depth;ansmax(ans,depth);//更新深度最大值// 先左后右子结点编号入队if(tree[id].ls!-1){tree[tree[id].ls].depthdepth1;//设置左子节点的深度q.push(tree[id].ls);}if(tree[id].rs!-1){tree[tree[id].rs].depthdepth1;//设置右子节点的深度q.push(tree[id].rs);}}}intmain(){// 读入和保存树cinn;for(inti1;in;i)cintree[i].lstree[i].rs;// 从根结点开始层序遍历bfs();// 输出coutansendl;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(1in-1)个数表示编号为i1的节点的父亲节点编号数据保证是一棵二叉树。第三行一个长度为n的01串从左到右第i(1≤in)位如果为0表示编号为i的节点颜色为白色否则为黑色。第四行一个正整数q表示操作次数。接下来q行每行一个正整数 a_i(1a_i≤n)表示第i次操作选择的节点编号。【输出描述】输出一行一个长度为n的 01串表示q次操作全部完成之后每个节点的颜色。从左到右第i(1i≤n)位如果为0表示编号为i的节点颜色为白色否则为黑色。【输入样例】63 1 1 3 41001013132【输出样例】010000#includeiostreamusingnamespacestd;#defineLEN100000structtree_node{intson[2];//子结点编号intvalue;};tree_node tree[LEN];intn,times;chartmp[LEN];//操作以rootid为根的所有结点值翻转voidprocess(introotid){if(rootid0)return;//空节点不处理tree[rootid].value1-tree[rootid].value;//0-1,1-0process(tree[rootid].son[0]);process(tree[rootid].son[1]);}intmain(){// 读入和保存树cinn;for(inti1;in-1;i){intid;cinid;if(tree[id].son[0]0)tree[id].son[0]i1;elsetree[id].son[1]i1;}cintmp;for(inti0;in;i){tree[i1].valuetmp[i]-0;}cintimes;//操作次数for(inti1;itimes;i){intid;cinid;process(id);}//输出for(inti1;in;i){couttree[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 则表示没有左右儿子。【输出描述】输出一个整型数 表示树的宽度。【输入样例】32 3-1 -1-1 -1【输出样例】2【输入样例】72 73 64 5-1 -1-1 -1-1 -1-1 -1【输出样例】2【提示】使用队列逐层遍历统计每层节点数最大值就是树的宽度。#includeiostream#includequeueusingnamespacestd;structtree_node{intls,rs;//ls:左孩子结点编号rs右孩子结点编号intdepth;//深度 即层号};tree_node tree[11];queueintq;// 为了节约空间队列中只保存树的编号intn;intwidth[11];// 层宽度数组第i层宽度width[i]voidbfs(){// 根结点编号1入队tree[1].depth1;//根节点在第1层q.push(1);while(!q.empty()){intidq.front();q.pop();//按层统计宽度intdepthtree[id].depth;width[depth];// 先左后右非空子结点编号入队if(tree[id].ls!-1){tree[tree[id].ls].depthdepth1;//设置左子节点的深度q.push(tree[id].ls);}if(tree[id].rs!-1){tree[tree[id].rs].depthdepth1;//设置右子节点的深度q.push(tree[id].rs);}}}intmain(){// 读入和保存树cinn;for(inti1;in;i)cintree[i].lstree[i].rs;// 从根结点开始层序遍历bfs();// 找到宽度最大值并输出intmax_width0;for(inti1;in;i)max_widthmax(max_width,width[i]);coutmax_widthendl;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。【输出描述】输出一个整数代表答案。【输入样例】71 6 5 4 3 2 1【输出样例】2对于所有评测用例1≤ N 10^5,0 |Ai| 10^5【提示】完全二叉树的第k层有2^k个结点(第一层k0)因此可以通过计数的方式在枚举数组的同时分别累计每个深度的结点数量。一旦某一层累加的结点数足够了就记录并比较大小然后初始化各个数据重新再累加计算。#includeiostream#includecmathusingnamespacestd;intmain(){intn;cinn;intcnt0,k0,sum0,ans0,ans20;//cnt计数k控制每一层是2的几次方个sum求和ans1记录最大值ans2记录深度for(inti0;in;i){intx;cinx;cnt;sumx;if(cntpow(2,i)||in-1){//计数2^k个或者累加到了最后一个结点cnt0;k;if(sumans){anssum;ans2k;}sum0;}}coutans2endl;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 */