LeetCode二叉树的公共祖先

题目链接

LeetCode二叉树的公共祖先

 

题目描述 

 

 

 思路解析：

ps:我这里看的是灵神的递归解题思路，我觉得很好理解；

关键思路拆解

1. 关键思路拆解

   • 终止条件的设计
     当递归遇到null（没找到）或直接遇到p/q时，返回当前节点。这一步的意义是：

     • 若找到p或q，则将其向上传递作为 “候选祖先”；
     • 若没找到（返回null），则表示当前子树中没有p或q。

   • 递归的本质
     算法通过递归深入左右子树，本质是后序遍历：先探索完所有子节点，再通过返回值判断当前节点是否为公共祖先。

   • 公共祖先的判定

     • 若左子树返回非空（找到一个节点），右子树也返回非空（找到另一个节点），说明p和q分别在当前节点的两侧，因此当前节点就是最近公共祖先。
     • 若只有左子树返回非空，说明p和q都在左子树中，左子树的返回结果就是它们的公共祖先（可能是其中一个节点本身，或更深层的公共祖先）。
     • 同理，若只有右子树返回非空，结果为右子树的返回值。

 

完整代码： 

疑难点： 

问：lowestCommonAncestor 函数的返回值是什么意思？

答：返回值的准确含义是「最近公共祖先的候选项」。对于最外层的递归调用者来说，返回值是最近公共祖先的意思。但是，在递归过程中，返回值可能是最近公共祖先，也可能是空节点（表示子树内没找到任何有用信息）、节点 p 或者节点 q（可能成为最近公共祖先，或者用来辅助判断上面的某个节点是否为最近公共祖先）。

问：为什么发现当前节点是 p 或者 q 就不再往下递归了？万一下面有 q 或者 p 呢？

答：如果下面有 q 或者 p，那么当前节点就是最近公共祖先，直接返回当前节点。如果下面没有 q 和 p，那既然都没有要找的节点了，也不需要递归，直接返回当前节点。

 

示例说明（以普通二叉树为例）

假设有如下二叉树，求p=4和q=5的最近公共祖先：

 

• 递归遍历左子树（5 的子树）时，会找到5和4，因此左子树返回5；
• 递归遍历右子树（1 的子树）时，未找到5或4，返回null；
• 因此当前节点3的左子树非空、右子树为空，最终返回左子树的结果5（即4和5的最近公共祖先是5）。

算法特点

• 时间复杂度：O (n)，其中 n 是二叉树的节点数。每个节点最多被访问一次。
• 空间复杂度：O (h)，其中 h 是二叉树的高度。递归栈的深度取决于树的高度（最坏情况为链状树，h=n）。
• 适用场景：任意二叉树（无需依赖节点值的大小关系，与二叉搜索树的 LCA 算法不同）。

 

灵神YYDS！！！