二叉搜索树的最近公共祖先（lca）利用bst左小右大的性质直接定位：若p、q分别位于当前节点左右子树或其一等于当前节点，则该节点即为lca；时间复杂度o(h)，无需额外空间。
什么是二叉搜索树的最近公共祖先（LCA）
在二叉搜索树（BST）中，最近公共祖先不是靠遍历+哈希表找路径，而是利用 BST 左小右大的性质直接向下定位。只要两个目标节点 p 和 q 分别落在当前节点的左右子树（或其中一个等于当前节点），这个当前节点就是 LCA。
关键判断逻辑是：root->val 与 p->val、q->val 的大小关系。不需要额外空间存路径，时间复杂度 O(h)，h 是树高。
递归写法：用 BST 性质剪枝
递归的核心是提前终止——一旦发现 p 和 q 在当前节点两侧，或其中一个是当前节点，就立刻返回，不继续深入无关子树。
- 如果
p->val和q->val都小于root->val，说明都在左子树，递归进root->left - 如果都大于
root->val，递归进root->right - 否则（一左一右，或有一个相等），当前
root就是 LCA，直接返回
示例代码片段：
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root) return nullptr;
int val = root->val, pval = p->val, qval = q->val;
if (pval left, p, q);
if (pval > val && qval > val)
return lowestCommonAncestor(root->right, p, q);
return root; // p 和 q 分居两侧，或其一为 root
}
迭代写法：避免递归栈开销
BST 的 LCA 迭代比普通二叉树更简洁——不用维护父指针或路径栈，只需一个 while 循环按大小关系移动指针。
- 初始化
curr = root - 循环条件：只要
curr不为空，且p和q不“夹住”curr（即未满足 LCA 条件），就持续更新curr - 更新规则和递归一致：全小 → 左走；全大 → 右走；否则跳出并返回
curr
注意：迭代版没有函数调用开销，对极深树更安全，且逻辑更贴近人脑推演过程。
容易踩的坑：BST 前提被忽略
很多人直接套用普通二叉树 LCA 的后序遍历解法，但那需要两次 DFS 找路径，时间 O(n)，且不依赖 BST 结构。如果题目明确是 BST，硬写通用解法就浪费了性质，还可能因节点值重复或输入非 BST 导致逻辑错乱。
- 务必确认输入确实是 BST（题目说“二叉搜索树”，不是“二叉树”）
- 不要假设
p->val val，比较时要独立判断两个值和root->val的关系 - 空节点检查不能漏——特别是递归基和迭代循环条件
- LeetCode 上该题（235）测试用例包含
p == q的情况，上述逻辑天然支持（因为“其中一个等于 root”会被捕获）
真正麻烦的从来不是写代码，而是没意识到 BST 的有序性已经把搜索压缩到了一条路径上。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
