为什么 lowestCommonAncestor 不能只靠递归返回 bool 判断存在性

很多初学者写完递归逻辑，发现对 root == p 或 root == q 直接返回 true，最后却找不到祖先节点——因为只返回布尔值，丢失了“哪个子树真正找到了目标节点”的信息。必须让递归返回实际的节点指针，才能在父节点层做合并判断。

正确做法是：每个子调用返回找到的 p、q 中的任意一个（或 nullptr），当前节点根据左右结果和自身是否匹配，决定返回谁。

• 如果左子树返回非空且右子树返回非空 → 当前节点就是 LCA
• 如果左非空、右为空，且当前节点不是 p 或 q → 返回左结果（说明祖先在左子树）
• 如果当前节点等于 p 或 q，且另一侧子树返回非空 → 当前节点是 LCA
• 否则，返回非空一侧（或 nullptr）

TreeNode* 递归函数的设计要点

函数签名必须是 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)，返回类型不能是 bool 或 void。核心逻辑围绕三个条件分支展开：

if (!root || root == p || root == q) return root;
<p>TreeNode<em> left = lowestCommonAncestor(root->left, p, q);
TreeNode</em> right = lowestCommonAncestor(root->right, p, q);</p><p>if (left && right) return root;           // p 和 q 分居两侧
if (left) return left;                   // p/q 全在左子树，或其中一个是 root
if (right) return right;                 // p/q 全在右子树
return nullptr;                          // 都没找到
</p>

注意：root == p 或 root == q 时直接返回 root，这既处理了“自身即目标”的情况，又保证了向上透传该节点引用——这是能正确合并的关键。

遇到 nullptr 或重复节点时的健壮性处理

实际输入可能含空指针、p == q、或 p/q 不在树中。标准解法默认假设 p 和 q 一定存在且互异，但生产代码应前置校验：

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

• 若 !p || !q || !root，直接返回 nullptr
• 若 p == q，可直接返回 p（LCA 就是它自己）
• 若不确定节点是否在树中，需额外一次遍历确认可达性；否则递归可能返回 nullptr，不代表出错，而是未找到

不校验时，函数行为仍是定义良好的：返回 nullptr 表示不存在公共祖先（即至少一个节点不在树中）。

迭代解法为何不推荐用于此题

虽然可用 parent 指针 + 哈希表回溯路径实现迭代版 LCA，但 C++ 标准 TreeNode 定义通常不含 parent 成员（LeetCode 等平台提供的结构体就是如此）。强行维护父映射需额外 O(n) 空间与一次 DFS 预处理，时间和代码复杂度都高于递归解。

递归本身只有 O(h) 栈空间（h 为树高），逻辑清晰无副作用，是本题最自然的选择。除非题目明确禁止递归或要求 O(1) 空间，否则不必绕路。

真正容易被忽略的是：递归返回值语义必须统一——始终代表“在以当前节点为根的子树中，找到的 p 或 q 的最近代表”，而不是“是否找到”。这个抽象一旦混淆，整个逻辑就会崩掉。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！