可以做图接单的网站广州网站建设 推广公司

可以做图接单的网站,广州网站建设 推广公司,动画制作设计,公司管理app有哪些这一题的大意是说给出前序遍历和后序遍历#xff0c;让我们找是否构造一个唯一的二叉树#xff0c; 如果可以返回Yes#xff0c;并输出中序遍历序列#xff0c;如果不可以#xff0c;那么就是输出No#xff0c;并输出其中一种情况的中序遍历序列。 我们都知道通过前序和后…这一题的大意是说给出前序遍历和后序遍历让我们找是否构造一个唯一的二叉树如果可以返回Yes并输出中序遍历序列如果不可以那么就是输出No并输出其中一种情况的中序遍历序列。我们都知道通过前序和后序是无法确定一棵二叉树的因为我们无法确定左子树和右子树分别是哪些它不像中序遍历后序遍历一样可以找到根节点后通过根节点把左右子树分开而前序和后序是无法实现的我们无法确定哪些是左子树哪些是右子树。因此我们要假设某一个节点前序节点中根节点的后面的那一个节点是左子树用这种方法来建树如果在建树的过程中如果存在前序遍历的左子树和后序遍历的右子树相等也就是后序遍历根节点的前一个节点和前序遍历的根节点的后一个节点相同。如果一样说明不能构成唯一的序列因为后序遍历根节点的前一个节点和前序遍历的根节点的后一个节点相同说明这个节点充当左子树和充当右子树是一样的。因此不唯一。我们通过遍历序列来建树的方法是有套路的boolflag1;//假设为一node*build(intprestart,intpreend,intpoststart,intpostend){if(prestartpreend){returnnullptr;}if(prestartpreend){//为啥在只有一个节点的时候不能继续往下划分node*rootnew(node);root-datapre[prestart];root-lnullptr;root-rnullptr;returnroot;}node*rootnew(node);root-datapre[prestart];root-lnullptr;root-rnullptr;intxpre[prestart1];//左子树的根节点if(pre[prestart1]post[postend-1]){flag0;}intindex;for(intipoststart;ipostend;i){if(post[i]x){indexi;break;}}intlenindex-poststart1;//这就是左子树的长度root-lbuild(prestart1,prestart1len-1,poststart,poststartlen-1);root-rbuild(prestart1len,preend,poststartlen,postend-1);returnroot;}这与之前的前序中序/中序后序建树的方法不同的是if(prestartpreend){node*rootnew(node);root-datapre[prestart];root-lnullptr;root-rnullptr;returnroot;}当子树只有一个节点的时候我们需要特判直接返回。为什么因为在后面建树的时候intxpre[prestart1];//左子树的根节点这里很明显越界了往后的遍历也会出错后面在递归划分左右子树也是错的因此我们要在只有一个节点的时候特判返回其他和中序后序建树是类似的。可以看一下这篇博客PAT 1020 Tree Traversals因此这一题的完整代码就如下啦#includebits/stdc.h#includeiostreamusingnamespacestd;intN;vectorintpre;vectorintpost;structnode{intdata;structnode*l;structnode*r;};boolflag1;//假设为一node*build(intprestart,intpreend,intpoststart,intpostend){if(prestartpreend){returnnullptr;}if(prestartpreend){//为啥在只有一个节点的时候不能继续往下划分node*rootnew(node);root-datapre[prestart];root-lnullptr;root-rnullptr;returnroot;}node*rootnew(node);root-datapre[prestart];root-lnullptr;root-rnullptr;intxpre[prestart1];//左子树的根节点if(pre[prestart1]post[postend-1]){flag0;}intindex;for(intipoststart;ipostend;i){if(post[i]x){indexi;break;}}intlenindex-poststart1;//这就是左子树的长度root-lbuild(prestart1,prestart1len-1,poststart,poststartlen-1);root-rbuild(prestart1len,preend,poststartlen,postend-1);returnroot;}boolf0;voidinorder(node*root){if(root-l!nullptr)inorder(root-l);if(root!nullptr){if(f0){coutroot-data;f1;}elsecout root-data;}if(root-r!nullptr)inorder(root-r);}intmain(){intN;cinN;for(inti0;iN;i){intx;cinx;pre.push_back(x);}for(inti0;iN;i){intx;cinx;post.push_back(x);}node*rootbuild(0,N-1,0,N-1);//cout1endl;if(flag1){coutYesendl;}else{coutNoendl;}inorder(root);coutendl;return0;}注意在最后的中序遍历后要加一个换行否则会报格式错误。总结这一题仍是典型的根据遍历序列来建树唯一不同的时候我们要假设左子树是哪些节点。因为只知道前序遍历和后序遍历序列是无法构成唯一的二叉树的。我们要根据题意判断建成的树是否唯一。