后序递归解法最优：每个节点仅访问一次，通过返回值传递子树含目标节点信息，并在回溯时判断LCA；需验证p、q存在性，避免静默错误。
用递归解法直接返回 LCA 节点，别存路径
想快，就别走“先找路径再比对”的老路——那要两次遍历+额外空间。Python 里最简练的解法是后序递归：每个节点只访问一次，靠返回值传递子树是否含目标节点的信息，同时在回溯时判断当前是否为 LCA。
核心逻辑是：若左子树和右子树分别找到 p 和 q，当前节点就是 LCA；若只有一边找到，且当前节点是 p 或 q，那它自己就是 LCA。
注意几个关键点：
-
None表示没找到目标节点；非None返回值一定是某个目标节点（p或q）或已确定的 LCA 节点 - 必须用
is判断节点相等（不是==），因为树节点不重载比较逻辑，且可能有重复值 - 递归终止条件要早于左右子树调用，否则空节点会抛 AttributeError
代码必须处理 p 和 q 相同、或其中一个不在树中的情况
题目常默认 p 和 q 一定存在且不同，但真实场景中漏判会导致静默错误或返回错节点。稳妥做法是加一层封装，先验证有效性：
立即学习“Python免费学习笔记（深入）”；
- 如果
p is q，直接返回p - 用一次 DFS 检查
p和q是否都在树中（可复用同一递归函数，加计数器或布尔标记） - 若任一节点不存在，按需返回
None或抛ValueError
常见坑：有人把 “找不到” 和 “LCA 是根” 混淆，比如整棵树只有 p，而 q 根本不存在，此时不应返回根节点。
TreeNode 定义影响写法，别硬套 LeetCode 默认结构
LeetCode 的 TreeNode 通常只有 val、left、right，但你自己定义时若加了 parent 指针，就能用 O(h) 时间向上遍历找交点——这时就不该用递归，而该用集合存一条路径，再查另一条路径首个命中节点。
- 有
parent：用set存p到根的全部节点，再从q向上找第一个在 set 中的节点 - 无
parent（标准情况）：坚持后序递归，时间 O(n)，空间 O(h) - 若树极度不平衡（链状），递归深度可能爆栈，可改用栈模拟递归，但实际中极少需要
测试时容易忽略的边界 case
写完别急着提交，这几个 case 一跑就露馅：
-
p是q的祖先（或反过来）：LCA 应是祖先节点，不是更深层那个 - 树只有一个节点，且它等于
p和q：应返回该节点 -
p和q在同一子树中：不能提前剪枝，必须完整遍历子树才能确认 - 空树输入：
root is None时直接返回None，别让递归进下一层
真正难的不是写对逻辑，而是记住：LCA 的定义依赖“存在性”和“最近性”两个前提，缺一不可。少验一个，线上就可能返回任意节点。
