3月31日刷题笔记--最近公共祖先（LCA）

本篇题目#

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

Medium

LeetCode 236 · 二叉树的最近公共祖先#

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

Medium

思路#

核心思想：递归遍历整棵树，用返回值来”上报”是否找到了 p 或 q。

递归的返回值含义：当前子树里有没有 p 或 q，有则返回找到的节点，没有则返回 None。

终止条件：遇到 None 直接返回 None；遇到 p 或 q 直接返回该节点，不再往下找。

递归逻辑：对左右子树分别递归，根据左右子树的返回值来判断 LCA 在哪里。

1
情况1：left 有值，right 有值  → p 和 q 分居两侧，当前 root 就是 LCA
2
情况2：left 有值，right 为空  → p 和 q 都在左子树，返回 left
3
情况3：left 为空，right 有值  → p 和 q 都在右子树，返回 right
4
情况4：left 为空，right 为空  → 当前子树没有 p 或 q，返回 None（被情况3顺带处理）

代码#

1
# Definition for a binary tree node.
2
# class TreeNode:
3
#     def __init__(self, x):
4
#         self.val = x
5
#         self.left = None
6
#         self.right = None
7

8
class Solution:
9
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
10
        if not root: return root          # 到底了，返回 None
11
        if root == p or root == q: return root  # 找到 p 或 q，直接上报
12

13
        left = self.lowestCommonAncestor(root.left, p, q)    # 左子树有没有
14
        right = self.lowestCommonAncestor(root.right, p, q)  # 右子树有没有
15

16
        if not left: return right   # 左边没有，答案在右边（含两者都没有的情况）
17
        if not right: return left   # 右边没有，答案在左边
18

19
        return root                 # 左右都有，当前节点就是 LCA

关键细节#

为什么遇到 p 就直接返回，不继续往下找 q？

题目保证 p 和 q 都存在于树中。如果 q 是 p 的子节点，那 p 本身就是 LCA，不需要找到 q 才能确定答案。提前返回 p，上层调用收到这个返回值就能正确判断。

if not root: return root 为什么不直接写 return None？

两者效果完全一样，root 此时就是 None。写 return root 只是习惯，看起来对称，实际没区别。

if not left: return right 涵盖了哪几种情况？

1
left = None, right = None  → 返回 right（即 None），说明这棵子树没有 p/q
2
left = None, right = 节点  → 返回 right，p/q 都在右子树

“左右都没找到”这种情况被第一行顺带处理了，不需要单独判断。

比较节点用 root == p，不能用 root.val == p

p 是 TreeNode 对象，不是数字。root.val == p 类型不匹配，会得到错误结果。如果要用 val 比较，要写 root.val == p.val，但不推荐，因为不同节点可能有相同的值。

隐含前提：p 和 q 一定存在于树中

如果不保证这一点，代码就不再正确。比如只有 p 存在而 q 不存在时，遍历完整棵树后 right 为 None，最终返回的是 p，而不是 None（表示找不到）。需要额外用 (node, found_count) 的方式来追踪是否真的找到了两个节点。

总结#

核心技巧：递归返回值做”信使”，把子树的查找结果逐层向上传递
LCA 判断：左右子树各自返回非空，说明 p 和 q 分居两侧，当前节点就是答案
复杂度：时间 O(n)，每个节点最多访问一次；空间 O(h)，h 为树高（最坏 O(n)，平衡树 O(log n)）

返回值情况	left	right	返回
p/q 分居两侧	有值	有值	root（当前即 LCA）
都在左子树	有值	None	left
都在右子树	None	有值	right
当前子树无 p/q	None	None	None（right）