企业官网建设流程全解析

做化妆品等的网站,app开发需要的技术,海淀公司网站搭建,国外网络ip地址先序遍历、中序遍历和后序遍历 时间限制#xff1a;1秒 空间限制#xff1a;256M 网页链接 牛客tracker 牛客tracker 每日一题#xff0c;完成每日打卡#xff0c;即可获得牛币。获得相应数量的牛币#xff0c;能在【牛币兑换中心】#xff0c;换取相应奖品1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述给定一棵包含n nn个节点的二叉树节点编号为1 ∼ n 1∼n1∼n以n − 1 n−1n−1条有向边( a i , b i ) (a_i,b_i)(ai​,bi​)形式给出表示父节点a i a_iai​指向子节点b i b_ibi​。对子节点的左右关系作如下规定若父节点拥有两个孩子则编号较小者为左孩子较大者为右孩子若父节点仅有一个孩子且该子节点编号大于父节点编号则视为左孩子否则视为右孩子。请输出该二叉树的先序、中序、后序遍历序列。输入描述第一行输入整数n ( 1 ≦ n ≦ 10 5 ) n(1≦n≦10^5)n(1≦n≦105)。接下来n − 1 n−1n−1行每行输入两个整数a i , b i ( 1 ≦ a i , b i ≦ n ) a_i,b_i(1≦a_i,b_i≦n)ai​,bi​(1≦ai​,bi​≦n)表示一条有向边a i → b i a_i→b_iai​→bi​。输出描述第一行输出先序遍历序列第二行输出中序遍历序列第三行输出后序遍历序列。各行序列中的数字以单个空格分隔。示例1输入2 1 2输出1 2 2 1 2 1解题思路首先构建二叉树结构用数组t tt存储每个节点的左右孩子遍历输入的n − 1 n-1n−1条有向边标记子节点v [ b ] t r u e v[b]truev[b]true按规则确定左右孩子父节点单孩子时子节点编号大于父节点则为左孩子否则为右孩子双孩子时编号较小者为左孩子随后找到未被标记的根节点无父节点接着通过递归分别实现先序根→左→右、中序左→根→右、后序左→右→根遍历依次输出对应序列该方法通过数组高效存储节点的左右孩子递归遍历适配n nn达1 e 5 1e51e5的规模先完成树的构建再按遍历规则输出精准得到三种遍历序列满足题目对左右孩子的定义和遍历顺序的要求。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefpairll,llpii;constll p1e97;constll N1e510;ll t[N][2];boolv[N];voidpro(ll root){coutroot ;if(t[root][0])pro(t[root][0]);if(t[root][1])pro(t[root][1]);}voidin(ll root){if(t[root][0])in(t[root][0]);coutroot ;if(t[root][1])in(t[root][1]);}voidpost(ll root){if(t[root][0])post(t[root][0]);if(t[root][1])post(t[root][1]);coutroot ;}intmain(){ll n;cinn;for(ll i1;in;i){ll a,b;cinab;v[b]true;if(t[a][0]0t[a][1]0){if(ab)t[a][0]b;elset[a][1]b;}else{if(t[a][0]){if(t[a][0]b)t[a][1]b;else{t[a][1]t[a][0];t[a][0]b;}}elseif(t[a][1]){if(t[a][1]b)t[a][0]b;else{t[a][0]t[a][1];t[a][1]b;}}}}ll root1;for(root1;rootn;root){if(!v[root])break;}pro(root);coutendl;in(root);coutendl;post(root);return0;}