后序遍历递归最稳健，每个节点返回None、p、q或其LCA；终止条件必须为if not root or root==p or root==q；左右子树均非空则root为LCA，否则返回非空者。
递归分治怎么写才不漏 case？
直接用后序遍历递归是最常用也最稳健的做法，核心在于：**每个节点只返回三种可能——None、p、q，或它们的 LCA**。不是“找路径”，而是“问子树：你见过 p 或 q 吗？”
- 终止条件必须写全：
if not root or root == p or root == q—— 缺了root == p或root == q，就无法处理“其中一个节点本身就是祖先”的情况（比如p=5, q=4时答案是5） - 左右子树结果要分清逻辑：
left_lca和right_lca都非空 → 当前root就是 LCA；只有一个非空 → 直接返回它（说明 p/q 全在那一侧） - 别用
and/or简写混淆语义，比如return left_lca or right_lca是对的，但若中间加了判断逻辑，容易错判None和布尔值
示例关键片段：
def lowestCommonAncestor(self, root, p, q):
if not root or root == p or root == q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right:
return root
return left or right
为什么不用父节点记录法？
虽然从 p、q 向上回溯找第一个共同父节点听起来直观，但在纯二叉树中——没有 parent 指针，硬加会导致空间翻倍、代码变重，且面试/线上题基本不给改结构。
- 你需要先 DFS 一遍建哈希表：
parent_map[node] = parent，额外O(n)空间和时间 - 再分别从 p、q 往上走，存路径，最后比对——实际是模拟了两次向上遍历，不如后序递归一次到位
- 如果题目明确说“树带 parent 字段”或要求支持多次查询，那另说；否则属于过度设计
路径比较法适合什么场景？
当你需要**调试过程**、或题目附带要求“返回从根到 p/q 的路径”时，路径比较法反而更直白可控。
立即学习“Python免费学习笔记（深入）”；
- 本质是两次 DFS + 一次数组扫描，时间仍是
O(n)，但空间最坏O(n)（链状树时路径存满） - 容易出错点：回溯时忘了
path.pop()，导致路径污染；或比较循环没加break，继续往后比造成误判 - 注意 Python 中列表切片比较要小心：
path_p[:i] == path_q[:i]不如逐个索引比更清晰，避免越界
BST 场景下千万别套通用解法
如果输入确定是二叉搜索树（BST），递归分治可以优化成 O(h) 时间、O(1) 空间迭代，而通用解法仍要 O(n) 时间。
- BST 性质决定了：若
p.val和q.val一左一右（即min(p.val,q.val) ），<code>root就是 LCA - 否则，全小于往左走，全大于往右走——连递归都不用，一个 while 就搞定
- 常见坑：用
==比较TreeNode实例（应比值或用is判同一对象），或忽略 BST 值唯一性假设，加多余存在性检查
真正卡住人的，往往不是“会不会写递归”，而是没意识到：BST 的 LCA 本质上是个二分查找问题，跟树形结构关系不大。
