185.二叉树：二叉搜索树的最近公共祖先（力扣）

代码解决

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    // 函数用于寻找二叉搜索树中节点 p 和 q 的最低公共祖先
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        // 如果当前节点为空，返回空
        if(root == NULL) return NULL;

        // 如果当前节点的值大于 p 和 q 的值，说明 p 和 q 都在左子树
        if(root->val > p->val && root->val > q->val)
        {
            // 递归查找左子树中的 LCA
            TreeNode* left1 = lowestCommonAncestor(root->left, p, q);
            // 如果在左子树中找到了 LCA，直接返回
            if(left1 != NULL) return left1;
        }

        // 如果当前节点的值小于 p 和 q 的值，说明 p 和 q 都在右子树
        if(root->val < p->val && root->val < q->val)
        {
            // 递归查找右子树中的 LCA
            TreeNode* right1 = lowestCommonAncestor(root->right, p, q);
            return right1; // 返回右子树中的 LCA
        }

        // 如果当前节点的值介于 p 和 q 之间，或者等于 p 或 q 的值，当前节点即为 LCA
        return root;
    }
};

代码使用了递归的方法。主要思路是首先判断当前节点是否为空，如果为空，返回空。然后，根据 p 和 q 的值与当前节点的值的关系，递归地在左子树或右子树中寻找这两个节点。如果当前节点的值大于 p 和 q 的值，则 p 和 q 都在左子树；如果当前节点的值小于 p 和 q 的值，则 p 和 q 都在右子树；如果当前节点的值介于 p 和 q 之间，或者等于 p 或 q 的值，则当前节点即为最低公共祖先。

这里简要解释一下代码的工作流程：

1. 首先判断当前节点是否为空，如果为空，返回空。
2. 根据 p 和 q 的值与当前节点的值的关系，决定在左子树或右子树中寻找这两个节点。
3. 递归地在选定的子树中寻找节点 p 和 q。
4. 根据递归的结果，判断当前节点是否为最低公共祖先，并返回结果。

这个算法的时间复杂度是 O(h)，其中 h 是树的高度。在最坏的情况下，可能需要遍历整个树来找到最低公共祖先。空间复杂度也是 O(h)，因为需要存储递归调用的栈。