网站开发报价表格专业外包

网站开发报价表格,专业外包,著名logo设计,开创者wordpress素材这一题的大意是给出一个BST的前序遍历#xff0c;让我们在这棵BST二叉树中#xff0c;给出两个的点#xff0c;判断这两个点在这棵二叉树的最近公共祖先是谁#xff0c;这两个点可能并不在树中#xff0c;也有可能给出的节点是另一个节点的祖先#xff0c;我们需要针对不…这一题的大意是给出一个BST的前序遍历让我们在这棵BST二叉树中给出两个的点判断这两个点在这棵二叉树的最近公共祖先是谁这两个点可能并不在树中也有可能给出的节点是另一个节点的祖先我们需要针对不同情况做出不同的判断。因为题目给出的节点的值是在int范围内也就是说这个值可能会很大我们可以选择离散化把N个值映射到1-N这样我们就可以用int depp[10005]直接来表示某一个节点的深度了。与unordered_mapint,int来说速度更快了因为是BST所以中序遍历的节点就是将所有值从小到大排序的结果。实际上不用离散化也可以吧可以参考这一题PAT 1151 LCA in a Binary Tree但BST中序遍历是升序的用离散化也可以在建树的过程中少写一个for循环查找中序遍历中根节点的位置。我们可以根据中序遍历和前序遍历来建树用哈希表来存储节点从而可以来找任意两个节点的公共祖先。因为只需要找公共祖先所以我们不用存储孩子节点只需要找到每一个节点的父亲节点和它的深度即可。根据前序遍历和中序遍历的建树方法已经写过多次了这里不再赘述在建好树后我们就需要关注如何找两个节点的最近公共祖先。我们只需要保证当深度相同时两个节点都去看它的父亲节点如果一个节点的深度比另一个节点大那么我们先去看这个深度深的节点同时看深度深的节点的祖先节点是否会等于另一个节点。 直到两个节点深度一样。大致思路就是如上完整代码如下#includebits/stdc.h#includeiostreamusingnamespacestd;intM;intN;unordered_mapint,intparent;vectorintpreorder;vectorintinorder;vectorinttemp;unordered_mapint,intlast;intdeep[10005];unordered_mapint,intmp;intbuild(intprestart,intpreend,intinstart,intinend,intd){if(prestartpreend||instartinend){return-1;}introotpreorder[prestart];deep[root]d;intindexroot-1;intlenindex-instart;intxlbuild(prestart1,prestartlen,instart,instartlen-1,d1);if(xl!-1)parent[xl]root;intxrbuild(prestartlen1,preend,instartlen1,inend,d1);if(xr!-1)parent[xr]root;returnroot;}intmain(){cinMN;for(inti0;iN;i){intx;cinx;preorder.push_back(x);}temppreorder;sort(temp.begin(),temp.end());for(inti0;itemp.size();i){mp[temp[i]]i1;last[i1]temp[i];temp[i]i1;}inordertemp;for(inti0;ipreorder.size();i){preorder[i]mp[preorder[i]];}introotbuild(0,N-1,0,N-1,0);intu;intv;for(inti0;iM;i){cinuv;if(!mp.count(u)!mp.count(v)){//如果u和v都不存在printf(ERROR: %d and %d are not found.\n,u,v);continue;}elseif(!mp.count(u)){printf(ERROR: %d is not found.\n,u);continue;}elseif(!mp.count(v)){printf(ERROR: %d is not found.\n,v);continue;}//现在要找最近公共祖先了//先把uv离散//如果它们不再同一层那么就需要把它们放到同一层inttempump[u];inttempvmp[v];if(temputempv){printf(%d is an ancestor of %d.\n,u,v);continue;}boolflag0;while(tempu!root||tempv!root){if(deep[tempu]deep[tempv]){if(parent[tempu]tempv){//说明v是u的ancestorflag1;printf(%d is an ancestor of %d.\n,v,u);break;}tempuparent[tempu];}elseif(deep[tempu]deep[tempv]){if(parent[tempu]parent[tempv]){flag1;printf(LCA of %d and %d is %d.\n,u,v,last[parent[tempu]]);break;}tempuparent[tempu];tempvparent[tempv];}else{if(parent[tempv]tempu){//说明u是v的ancestorflag1;printf(%d is an ancestor of %d.\n,u,v);break;}tempvparent[tempv];}}if(flag0){printf(LCA of %d and %d is %d.\n,u,v,last[parent[tempu]]);}}return0;}注意给出的两个节点可能是同一个我们要进行特判。inttempump[u];inttempvmp[v];if(temputempv){printf(%d is an ancestor of %d.\n,u,v);continue;}总结这一题就是BST建树最近公共祖先的求法我们用根据实际情况灵活建树。