【PAT甲级】LCA专题复习

清疚 2023-02-25 07:19 2阅读 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 条评论，2人围观）

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

相关阅读

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

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

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

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

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

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

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

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

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

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhp

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

相关 PAT甲级1147 Heaps

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

冷不防/ 2023年02月19日 09:24/ 0 赞/ 105 阅读

相关 PAT甲级1093 Count PAT

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

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

相关 PAT甲级1008. Elevator

The highest building in our city has only one elevator. A request list is made up with N

﹏ヽ暗。殇╰゛Y/ 2022年06月11日 02:36/ 0 赞/ 213 阅读

相关 PAT甲级解题目录

<table style="width:798.621px;text-align:center;border-style:solid;border-color:rgb(238,

梦里梦外;/ 2022年05月27日 00:40/ 0 赞/ 173 阅读

相关 PAT甲级C++总结（一）

1.min和max：返回a和b的最小值或最大值，有三个参数，前两个必需，为比较的参数，第三个为比较的方法，使用时需要加上头文件algorithm 2.C/C++，用0x3f3

﹏ヽ暗。殇╰゛Y/ 2022年01月27日 14:37/ 0 赞/ 230 阅读

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

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

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