bst中求最近公共祖先有四种方法：一是利用bst性质递归查找，根据目标节点值与当前节点值大小关系决定递归方向；二是迭代方式逐层定位，时间复杂度o(h)，空间复杂度o(1)；三是复用通用二叉树lca算法，通过路径比对求解；四是基于节点值范围判断的剪枝法，适用于指针不可靠场景。
一、利用BST性质递归查找
二叉搜索树中，任意节点的左子树所有节点值均小于该节点值，右子树所有节点值均大于该节点值。因此，当两个目标节点分别位于当前节点的左右两侧，或其中一个是当前节点时，当前节点即为最近公共祖先。此方法直接依据BST结构特性，无需额外空间存储路径。
1、定义递归函数，参数为根节点指针及两个目标节点指针。
2、若根节点为空，返回空指针。
3、获取当前节点值、目标节点p和q的值。
4、若p和q的值均小于当前节点值，则递归调用左子树。
5、若p和q的值均大于当前节点值，则递归调用右子树。
6、否则，当前节点即为最近公共祖先，返回该节点指针。
二、迭代方式逐层定位
基于BST的有序性，可避免递归调用栈开销，使用循环从根节点出发，根据节点值关系持续向下移动指针，直到找到分岔点或匹配节点。该方法时间复杂度为O(h)，空间复杂度为O(1)。
1、初始化当前节点为根节点。
2、进入循环，条件为当前节点非空。
3、若p和q的值均小于当前节点值，则将当前节点更新为其左子节点。
4、若p and q的值均大于当前节点值，则将当前节点更新为其右子节点。
5、否则，跳出循环并返回当前节点指针。
三、通用二叉树LCA逻辑适配BST
虽非最优，但可复用通用二叉树最近公共祖先算法框架：先获取从根到p和q的两条路径，再比对路径上最后一个相同节点。由于BST仍为二叉树，该方法逻辑上成立，适用于调试验证或教学对照场景。
1、编写辅助函数，通过递归获取从根到指定节点的路径，存入vector
2、分别调用该函数获取p和q的路径向量path_p和path_q。
3、遍历两个路径向量，比较对应位置节点指针是否相等。
4、记录最后一个相等的节点指针。
5、返回该节点指针作为结果。
四、基于节点值范围判断的剪枝法
不依赖节点地址比较，仅通过数值区间判定关系。设定当前子树有效值域[minVal, maxVal]，初始为[INT_MIN, INT_MAX]；当目标节点值落在当前节点左右子树对应区间内且跨立时，当前节点即为答案。适用于节点指针不可靠或需解耦数据与结构的场景。
1、定义递归函数，参数包括当前节点、值域上下界、目标值p_val和q_val。
2、若当前节点为空，返回空指针。
3、若p_val和q_val分别严格小于和大于当前节点值，返回当前节点指针。
4、若p_val和q_val均小于当前节点值，且当前节点左子节点存在，则递归进入左子树，更新上界为当前节点值减一。
5、若p_val和q_val均大于当前节点值，且当前节点右子节点存在，则递归进入右子树，更新下界为当前节点值加一。
6、若p_val或q_val等于当前节点值，直接返回当前节点指针。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
