解法：递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    // p,q都在左子树中
    if(p->val < root->val && q->val < root->val) return lowestCommonAncestor(root->left, p, q);
    // p,q都在右子树中
    else if(p->val > root->val && q->val > root->val) return lowestCommonAncestor(root->right, p, q);
    // p,q分别在root两边，root是最近公共祖先
    // p是root,q是它的子孙，root是最近公共祖先
    // q是root，p是它的子孙，root是最近公共祖先
    else return root;
}

时间复杂度 O ( n ) O(n) O(n):最坏情况，当二叉搜索树退化为一条链表，搜索深度最大为n
空间复杂度 O ( n ) O(n) O(n):最坏情况，当二叉搜索树退化为一条链表，递归调用的系统栈深度最大为n