LCA是深度最大的同时为两节点祖先的节点；递归解法通过后序遍历，以返回值传递子树是否含p/q或已找到LCA的信息，核心是左右非空则当前节点为LCA。
什么是LCA？先看最核心的判断逻辑
二叉树中两个节点的最近公共祖先（LCA），是指**深度最大的、同时是这两个节点祖先的节点**。关键不在于“怎么找”，而在于如何定义“祖先”和“最近”——它必须满足：从根出发，root能同时到达 p 和 q，且左右子树分别包含其中一个（或自身就是 p 或 q）。
递归解法：用返回值传递存在性信息
标准做法是后序遍历，每个节点返回：nullptr（子树里没 p 也没 q）、p、q 或 LCA 节点本身。核心逻辑在回溯时判断：
- 如果左子树返回非空，右子树也返回非空 → 当前
root就是 LCA - 如果只有一边非空 → 直接返回该非空指针（表示这一侧已找到目标，或已找到 LCA）
- 注意：一旦
root == p或root == q，立即返回root，不继续向下——这是保证“最近”的关键
示例片段（省略 TreeNode 定义）：
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || root == p || root == q) return root;
auto left = lowestCommonAncestor(root->left, p, q);
auto right = lowestCommonAncestor(root->right, p, q);
if (left && right) return root;
return left ? left : right;
}为什么不能用父指针或存储路径？常见误区
虽然用哈希表存每个节点的父节点再向上追溯也能做，但问题在于：
立即学习“C++免费学习笔记（深入）”；
- 题目给的是纯二叉树结构（无
parent指针），额外构建父链需要 O(n) 空间和预处理，违背“树形递归”的本意 - 存储从根到
p、q的两条路径再比对，时间 O(h)，空间 O(h)，但需两次遍历 + 额外容器，代码更冗长，且易在边界（如p是q祖先）出错 - 递归解法天然单次遍历、O(1) 额外空间（不算栈），且逻辑统一覆盖所有情况（含
p和q在同一子树的情形）
实际编码时容易漏掉的细节
这个函数看似短，但上线环境常因几个点 fail：
-
if (!root || root == p || root == q)缺少!root判断 → 空指针解引用 - 误写成
if (root == p || root == q) return root;忘了判空 → 运行时崩溃 - 把
left && right写成left || right→ 提前返回，得到的不是“最近”祖先 - 没有考虑
p或q不在树中的情况（题目通常保证存在，但工程代码建议加 assert 或提前校验）
真正难的不是写出来，而是想清楚“返回值代表什么”——它不是在标记“找到了”，而是在传递“我这个子树是否贡献了有效信息”。
