中国建设银行官网站汽车卡深圳个性化网站建设公司电话

中国建设银行官网站汽车卡,深圳个性化网站建设公司电话,网站开发基本构成,小游戏 打开【题目描述】 树和二叉树基本上都有先序、中序、后序、按层遍历等遍历顺序#xff0c;给定中序和其它一种遍历的序列就可以确定一棵二叉树的结构。 假定一棵二叉树一个结点用一个字符描述#xff0c;现在给出中序和按层遍历的字符串#xff0c;求该树的先序遍历字符串。 【输…【题目描述】树和二叉树基本上都有先序、中序、后序、按层遍历等遍历顺序给定中序和其它一种遍历的序列就可以确定一棵二叉树的结构。假定一棵二叉树一个结点用一个字符描述现在给出中序和按层遍历的字符串求该树的先序遍历字符串。【输入】两行每行是由字母组成的字符串一行的每个字符都是唯一的分别表示二叉树的中序遍历和按层遍历的序列。【输出】一行表示二叉树的先序序列。【输入样例】DBEAC ABCDE【输出样例】ABDEC【算法笔记】已知中序和层序怎么求先序(两种解法详解)0. 前言在二叉树遍历的题目中我们最常见的是“前序中序”或者“后序中序”求树。这种题目比较简单因为根节点总是躲在字符串的最头或者最尾一抓一个准。但是“中序 层序” 往往让人头大。因为层序遍历是按层级从上往下数的子树的根节点在字符串里是散落的不像前序/后序那样连续。今天就来拆解这道经典题目采用“建树求解”和“直接递归”两种解法。1. 核心逻辑谁是根不管用哪种写法破解这道题的核心逻辑只有一句话层序遍历负责“选老大”定根节点中序遍历负责“分地盘”划分子树。层序遍历 (Level Order)这是一张“权力排行榜”。不管这棵树长什么样排在层序遍历前面的节点辈分一定比后面的高。中序遍历 (In Order)这是一张“座位表”。根节点坐中间左子树的所有节点都在它左边右子树的所有节点都在它右边。解题三部曲查榜拿着层序遍历的名单去中序遍历的当前范围内找。谁在层序里出现得最早谁就是当前的根。分家找到了根中序遍历就被切成了两半——左边是左子树右边是右子树。递归对左右两半重复上述过程。2. 解法一正规建树法如果你不仅需要输出先序遍历后续还需要对这就棵树进行其他操作比如求高度、镜像翻转那么老老实实把树建起来是最稳妥的。思路解析开一个结构体数组tre[]存树用cnt动态分配节点编号。写一个build(L, R, u)函数L, R代表当前处理的是中序字符串a的[L, R]这一段。u代表当前节点的编号。在build内部找到根节点位置pos后递归build(L, pos-1, ...)去填tre[u].l(左孩子)。递归build(pos1, R, ...)去填tre[u].r(右孩子)。最后写一个preorder函数把树打印出来。//第一种做法 建树然后遍历 #include iostream #include string using namespace std; string a,b;//中序 层序 int cnt1;//节点计数器,从1号开始分配 struct node{ char data;//存字母 int l,r;//存左孩子和右孩子的下标编号 }tre[1005]; //L,R:当前范围下标,u:当前节点编号 void build(int L,int R,int u){ int pos-1;//用来存根节点在a中的下标 //遍历层序b,谁排在前面谁就是根 for(int i0;ib.length();i){ int ka.find(b[i]); //必须在当前范围[L,R]里才算数 if(kLkR){ tre[u].datab[i];//确定根 posk;//记下位置 break; } } //处理左子树 if(posL){ cnt; tre[u].lcnt; build(L,pos-1,cnt);//递归左边[L,pos-1] }else{ tre[u].l0; } //处理右子树 if(posR){ cnt; tre[u].rcnt; build(pos1,R,cnt);//递归右边[pos1,R] }else{ tre[u].r0; } } //先序遍历输出 void preorder(int u){ if(u0)return; couttre[u].data; preorder(tre[u].l); preorder(tre[u].r); } int main(){ cinab; build(0,a.size()-1,1); preorder(1); return 0; }3. 解法二直接输出法如果题目仅仅要求输出先序遍历不需要后续操作那我们完全可以省去建树的过程。思路解析先序遍历的顺序是根 - 左 - 右。我们完全可以利用递归函数的执行顺序来模拟这个过程在函数里找到根。直接cout这个根。递归调用函数处理左边。递归调用函数处理右边。这种写法不需要结构体不需要数组代码极短是考场上的拿分利器。//第二种做法 不建树 直接输出 #include iostream #include string using namespace std; string a,b;//中序 层序 //L为左边界下标 R为右边界下标 void dfs(int L,int R){ //如果左手跑到右手右边去了,说明范围空了,不干了 if(LR)return; int k; //拿着层序字符串(b)里的名字,一个一个去查 for(int i0;ib.size();i){ int posa.find(b[i]);//算出b[i]在中序的位置 //只要这个位置在我们当前的范围[L,R]里面,它就是根 if(posLposR){ kpos;//记下位置,等会用来切分 coutb[i];//先序遍历直接打印根 break;//找到了最大的,停 } } //递归处理左右两边 dfs(L,k-1);//处理k左边的 dfs(k1,R);//处理k右边的 } int main(){ cinab; //一开始的范围是:从0到最后一个 dfs(0,a.size()-1); return 0; }4. 总结与避坑哪个更好写法二直接输出代码量少逻辑清晰不容易写错推荐考试使用。写法一建树更通用。如果题目下一问是让你求树的深度或者求后序遍历写法一改动更小。常见坑点在 for 循环找根的时候千万不要找到一个 a.find(b[i]) 存在的就直接 break一定要加上 if (k L k R) 这个判断。因为 b 里的节点可能在 a 的其他部分比如已经在上一层的递归中被处理过了我们只关心当前这个子树范围内的节点。代码总结/* //第一种做法 建树然后遍历 #include iostream #include string using namespace std; string a,b;//中序 层序 int cnt1;//节点计数器,从1号开始分配 struct node{ char data;//存字母 int l,r;//存左孩子和右孩子的下标编号 }tre[1005]; //L,R:当前范围下标,u:当前节点编号 void build(int L,int R,int u){ int pos-1;//用来存根节点在a中的下标 //遍历层序b,谁排在前面谁就是根 for(int i0;ib.length();i){ int ka.find(b[i]); //必须在当前范围[L,R]里才算数 if(kLkR){ tre[u].datab[i];//确定根 posk;//记下位置 break; } } //处理左子树 if(posL){ cnt; tre[u].lcnt; build(L,pos-1,cnt);//递归左边[L,pos-1] }else{ tre[u].l0; } //处理右子树 if(posR){ cnt; tre[u].rcnt; build(pos1,R,cnt);//递归右边[pos1,R] }else{ tre[u].r0; } } //先序遍历输出 void preorder(int u){ if(u0)return; couttre[u].data; preorder(tre[u].l); preorder(tre[u].r); } int main(){ cinab; build(0,a.size()-1,1); preorder(1); return 0; } */ //第二种做法 不建树 直接输出 #include iostream #include string using namespace std; string a,b;//中序 层序 //L为左边界下标 R为右边界下标 void dfs(int L,int R){ //如果左手跑到右手右边去了,说明范围空了,不干了 if(LR)return; int k; //拿着层序字符串(b)里的名字,一个一个去查 for(int i0;ib.size();i){ int posa.find(b[i]);//算出b[i]在中序的位置 //只要这个位置在我们当前的范围[L,R]里面,它就是根 if(posLposR){ kpos;//记下位置,等会用来切分 coutb[i];//先序遍历直接打印根 break;//找到了最大的,停 } } //递归处理左右两边 dfs(L,k-1);//处理k左边的 dfs(k1,R);//处理k右边的 } int main(){ cinab; //一开始的范围是:从0到最后一个 dfs(0,a.size()-1); return 0; }