孝昌建设局网站24小时网站建设

孝昌建设局网站,24小时网站建设,西安地区网站建设,深圳沙井做网站公司【题目描述】输入一棵二叉树的先序和中序遍历序列#xff0c;输出其后序遍历序列。【输入】共两行#xff0c;第一行一个字符串#xff0c;表示树的先序遍历#xff0c;第二行一个字符串#xff0c;表示树的中序遍历。树的结点一律用小写字母表示。【输出】一行#xff0…【题目描述】输入一棵二叉树的先序和中序遍历序列输出其后序遍历序列。【输入】共两行第一行一个字符串表示树的先序遍历第二行一个字符串表示树的中序遍历。树的结点一律用小写字母表示。【输出】一行表示树的后序遍历序列。【输入样例】abdec dbeac【输出样例】debca【算法笔记】由先序和中序遍历还原二叉树别死记下标一张草稿纸搞定在二叉树的题目里“已知先序和中序求后序”属于必考的基本功。很多同学逻辑都懂先序找根中序分左右。但在写代码时往往死在递归的下标边界计算上。到底是1还是-1左子树的长度怎么算一不小心就写出个死循环。今天结合一张手写草稿带大家彻底理顺这个逻辑并给出顺序存储和链式存储两种标准写法。1. 核心思路对着草稿推下标看先序a b d e c和中序d b e a c。先序第一个a是根。去中序里找到a的位置它左边的d b e是左子树右边的c是右子树。难点在于如何在先序序列里把左子树那一段精准地“抠”出来关键变量定义我们在递归函数dfs(la,ra,lb,rb)中定义la,ra当前子树在先序中的起点和终点。lb,rb当前子树在中序中的起点和终点。root根节点在中序里的下标用 string 的 find 找到。必考逻辑请理解并背诵左子树有多长看中序序列从 lb 开始到 root 前面。所以左子树长度 (len) root - lb。(这一步算错后面全错)左子树的范围递归左儿子中序很明显是[lb, root-1]。先序起点是根的下一个la1。终点是起点加上长度。也就是[la1, laroot-lb]。右子树的范围递归右儿子中序很明显是[root1, rb]。先序紧接着左子树后面。起点左子树终点 1。也就是la(root-lb)1。终点直接就是ra。2. 方法一顺序存储完全二叉树思维利用完全二叉树性质节点k的左儿子下标是2*k右儿子是2*k1。优点逻辑简单。缺点极其浪费空间。如果是“歪脖子树”退化成链空间复杂度是 2^N。除非确定节点少或者满二叉树否则慎用。//先建树 再后序遍历输出 //方法一顺序存储 //特点利用2*k和2*k1计算位置 #includebits/stdc.h using namespace std; string a,b;//先序遍历 中序遍历 struct node{ int l;//记录左儿子节点的下标 int r;//记录右儿子节点的下标 char data; node(){ lr0; } }tre[4000];//顺序存储一定要开大数组防止越界 void postorder(int root){//后序输出 if(tre[root].l!0) postorder(root*2); if(tre[root].r!0) postorder(root*21); couttre[root].data; } void dfs(int la,int ra,int lb,int rb,int k){ //k代表所建树中根节点的下标 la ra代表本次先序遍历的起点终点 //lb rb代表本次中序遍历的起点终点 if(lara||lbrb) return; int rootb.find(a[la]);//找到根节点在中序遍历输出中的位置 tre[k].dataa[la];//顺序存储记录根节点的数据 if(rootlb){//代表有左子树 tre[k].l2*k;//顺序存储的特点 //左子树长度root-lb所以先序终点la(root-lb) dfs(la1,laroot-lb,lb,root-1,k*2); } if(rootrb){//代表有右子树 tre[k].r2*k1;//顺序存储的特点 //右子树先序起点la左子树长度1 dfs(laroot-lb1,ra,root1,rb,2*k1); } } int main(){ cinab; int raa.size(); int rbb.size(); dfs(0,ra-1,0,rb-1,1); postorder(1); return 0; }3. 方法二链式存储静态数组模拟打比赛最推荐的写法。不依赖 2*k而是用一个全局计数器 ind用一个申请一个。哪怕树退化成一条链世代单传二叉树空间复杂度也只是 O(N)。原理每次ind给新节点发一个“身份证号”父节点把这个号码记在l或r里。//方法二链式存储静态数组池 //特点空间利用率高通用性强 #includebits/stdc.h using namespace std; string a,b; struct node{ int l; int r; char data; node(){lr0;} }tre[1000]; int ind1;//链式存储存放结点位置 void postorder(int root){ if(tre[root].l!0) postorder(tre[root].l); if(tre[root].r!0) postorder(tre[root].r); couttre[root].data; } void dfs(int la,int ra,int lb,int rb,int k){ int rootb.find(a[la]);//找到根节点在b中的位置下标 tre[k].dataa[la]; if(rootlb){//如果左子树存在 tre[k].lind;//链式存储的特点申请新节点 dfs(la1,laroot-lb,lb,root-1,ind); } if(rootrb){//代表右子树存在 tre[k].rind;//链式存储的特点申请新节点 dfs(root-lbla1,ra,root1,rb,ind); } } int main(){ cinab; int raa.size()-1; int rbb.size()-1; dfs(0,ra,0,rb,1); postorder(1); return 0; }4. 避坑总结关于下标千万别死记laroot-lb这种一长串的东西。考试时像我一样在草稿纸上画一段算出左子树长度然后根据“起点长度”去推绝对不会错。关于存储如果是平时练习或者题目保证是完全二叉树 -用方法一写得快。如果是正式比赛或者不确定树的形状 -必用方法二稳不爆内存。关于代码风格大家注意看我在顺序存储里也保留了tre[k].l2*k。虽然这一步可以通过计算省略但加上去之后它和链式存储的逻辑就完全统一了非常适合理解“二叉树的本质”。