【PAT甲级】LCA专题复习

清疚 2023-02-25 07:19 57阅读 0赞

这个部分在《算法笔记》是没有的。

这种新背景的题目，如果之前没有接触过，那只能从普通的定义去解，即：

1.建树  
2.找祖先，找到一致的就是最低公共祖先

例子：[hihoCoder - 1062 、  ][hihoCoder - 1062 _][二叉树的公共父结点][Link 1]

但是如果之前接触过，就能立即从[递归的原理][Link 2]解：

假设要查找LCA的结点：  
1.是父子，父节点就是LCA  
2.在目前根的左右，则目前的根就是LCA  
3.目前在根的同一侧，则目前的根设为该侧的子节点，继续递归

真题：

<table> 
 <tbody> 
  <tr> 
   <th style="width:90px;">树、LCA</th> 
   <td style="width:157px;">18秋第四题</td> 
   <td>1151</td> 
   <td style="width:397px;"><a href="https://blog.csdn.net/allisonshing/article/details/104570744" rel="nofollow">LCA in a Binary Tree (30分)</a></td> 
  </tr> 
  <tr> 
   <th style="width:157px;">树、BST、LCA</th> 
   <td>17冬第四题</td> 
   <td>1143</td> 
   <td style="width:397px;"><a href="https://blog.csdn.net/allisonshing/article/details/104604908" rel="nofollow">Lowest Common Ancestor（30分）</a></td> 
  </tr> 
 </tbody> 
</table>

[hihoCoder - 1062 _]: https://blog.csdn.net/u014355480/article/details/43529767
[Link 1]: https://blog.csdn.net/weixin_42449444/article/details/86156602
[Link 2]: https://blog.csdn.net/qq_45732909/article/details/106031541

发表评论取消回复

表情：

评论列表（有 0 条评论，57人围观）

还没有评论，来说两句吧...

相关阅读

相关【PAT甲级】排序题专题复习

固定模式要排序的量一般放在一个或多个向量的结构体、unordered\_map或者set中，然后定义一个或多个cmp函数。（具体是几个就看题目将排序对象分成几种、有几个

深藏阁楼爱情的钟/ 2023年02月28日 04:29/ 0 赞/ 22 阅读

相关【PAT甲级】堆的专题复习

虽然《算法笔记》的9.7有介绍堆，1098题也是跟堆有关。但是在PAT甲级近三年的题目里，没考过向下调整、建堆写法，只了解到堆的概念就行。目前的考纲也没有明确地提到“堆”。近三

野性酷女/ 2023年02月28日 04:05/ 0 赞/ 22 阅读

相关【PAT甲级】LCA专题复习

这个部分在《算法笔记》是没有的。这种新背景的题目，如果之前没有接触过，那只能从普通的定义去解，即： 1.建树 2.找祖先，找到一致的就是最低公共祖先例子：[hih

清疚/ 2023年02月25日 07:19/ 0 赞/ 58 阅读

相关【PAT甲级】并查集专题复习

博主开始复习PAT甲级了，会做多个复习的专题，会解释需要注意的基本概念和题库相关的满分代码展示。目的：通过多刷题，多总结回顾，让自己在方法层面还是代码细节达到熟练写出的程度

迈不过友情╰/ 2023年02月23日 12:17/ 0 赞/ 140 阅读

相关【PAT甲级】Dijkstra专题复习

Dijkstra专题近三年考察情况：19年9月第四题（题解在此：[https://blog.csdn.net/allisonshing/article/details/1006

╰半橙微兮°/ 2023年02月23日 08:13/ 0 赞/ 60 阅读

相关 PAT甲级 2017-2019 第一题 && 字符串专题

[英语单词积累][Link 1] [算法笔记总目录][Link 2] 考点分析 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naG

谁践踏了优雅/ 2023年02月22日 05:27/ 0 赞/ 67 阅读

相关 PAT甲级1151 LCA in a Binary Tree LCA+DFS

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhp

清疚/ 2023年02月21日 06:51/ 0 赞/ 53 阅读

相关 PAT甲级1143 Lowest Common Ancestor BST+LCA

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhp

╰半橙微兮°/ 2023年02月21日 06:47/ 0 赞/ 55 阅读

相关 PAT甲级1093 Count PAT

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

柔光的暖阳◎/ 2023年02月14日 00:28/ 0 赞/ 85 阅读

相关 PAT甲级|1151 LCA in a Binary Tree 先序中序遍历建树 lca

给定先序中序遍历的序列，可以确定一颗唯一的树先序遍历第一个遍历到的是根，中序遍历确定左右子树查结点a和结点b的最近公共祖先，简单lca思路： 1.如果a和b分别

柔光的暖阳◎/ 2021年11月13日 19:54/ 0 赞/ 232 阅读