【LeetCode】升级打怪之路 Day 21：二叉树的最近公共祖先（LCA）问题

news/2024/7/26 23:41:16/文章来源:https://blog.csdn.net/qq_45668004/article/details/136679662

今日题目：

236. 二叉树的最近公共祖先
1644. 二叉树的最近公共祖先 II
235. 二叉搜索树的最近公共祖先

今天做了几道有关二叉树的最近公关祖先（LCA）问题，没有接触过的话，直接上手就能解答出来还是存在不少困难的。今天学习了相关的解题思路，寻找 LCA 问题的框架在本质上还是一个二叉树递归遍历的框架。重点需要把握好代码实现中辅助函数 find() 的语义，以及为什么这样实现。根据 LCA 可能出现的情况，实现 LCA 的寻找。

LCA 问题

最近公共祖先（Lowest Common Ancestor，LCA）问题是一类问题，这类题目也存在一定的难度，因此需要认真学习一下。

labuladong 的 Git原理之最近公共祖先这篇文章介绍了 LCA 问题的解题思路，可以参考学习一下。

LC 236. 二叉树的最近公共祖先【classic】

236. 二叉树的最近公共祖先

这个题目就是经典的 LCA 问题。

我们想要找 p 和 q 的 LCA，那这个 LCA 有两种情况：

case 1：自己是 p 或 q，另一个在自己的子树上（或者也还是自己）
case 2：自己不是 p 或 q，其中一个在自己左子树上，另一个在自己右子树上

对于寻找 LCA 的问题，我们可以写一个 find() 辅助函数来完成递归寻找。

我们需要明确一下 find() 函数的语义：它从 root 开始寻找它认为最可能是 LCA 的节点。这里限定是“最可能”是因为，在 case 1 中，如果一个节点发现自己是 p 或 q，那它就不需要再向下找了，因为从自己这个层次上来看，如果有 LCA 的话，那也只能是自己，不可能是再向下的子树中的节点了。至于真的是不是 LCA，就交由更上层的节点来验证，如果更上层的节点没有再找到另一个 p 或 q，那就是了。所以 find 函数只需要返回当前这个节点自认为最可能是 LCA 的节点就可以。来看代码：

236 题目

可以看到，find() 函数就是返回一个节点在自己层级上所认为的最可能是 LCA 的节点。因为题目说了一定存在 p 和 q，也就是一定存在 LCA，所以最终返回的就是 root 所认为的最可能是 LCA 的节点，它是一定存在的。

LC 1644. 二叉树的最近公共祖先 II 【稍有难度】

1644. 二叉树的最近公共祖先 II

这个题目相比于上个题目有了变动，上一个题目明确说了一定存在 LCA，但这个题目却不一定，所以在这题目中，我们无法肯定 find() 函数返回的最终结果就是 LCA，需要加一个标志位用来区分是否真的找到了 LCA。

在之前的 find() 函数的逻辑中，当一个节点自己就等于 p 或 q 之一时就返回自己作为可能的 LCA，没有再向下确定自己的子树中是否还存在另一个目标值，从而导致了这种不确定性。因为我们的遍历本质上是后序递归遍历，所以遍历一定是遍历了所有节点，也就是如果存在 p 或 q，我们是一定能遍历到的，所以我们可以加一个标志位来记录是否找到了 p 和 q。如果最终标志位说明找到了 p 和 q，那 find() 函数返回的 TreeNode 就是我们要找的 LCA 节点了。

所以这个题目的解法相比于上个题目，主要是加了个标志位：

1644
可以看到，代码整体思路与之前的一样，只是加了个标志位，用来判断最终找到的结果是不是 LCA。