题目的主要信息：

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先：

• 对于该题的最近的公共祖先定义：对于有根树T的两个结点p、q，最近公共祖先LCA(T,p,q)表示一个结点x，满足x是p和q的祖先且x的深度尽可能大
• 一个节点也可以是它自己的祖先
• 二叉搜索树是若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
• 所有节点的值都是唯一的，可以通过节点值直接比较
• p、q 为不同节点且均存在于给定的二叉搜索树中

方法一：两次遍历

具体做法：

二叉搜索树且没有相同值的节点，因此分别从根节点往下利用二叉搜索树找到p、q，在搜索的时候小于当前节点则进入左子树，大于该节点则进入右子树，直到找到相应节点，在这个过程中记录搜索路径。

有了从根节点到两个目标节点的搜索路径以后，比较两条路径，路径前面相同的部分都是两个节点在搜索时相同的祖先，即最后一次相同的节点就是最近公共祖先。

class Solution {
public:
    vector<int> getPath(TreeNode* root, int target) { //求得根节点到目标节点的路径
        vector<int> path;
        TreeNode* node = root;
        while (node->val != target) { //节点值都不同，可以直接用值比较
            path.push_back(node->val);
            if (target < node->val) //小的在左子树
                node = node->left;
            else //大的在右子树
                node = node->right;
        }
        path.push_back(node->val);
        return path;
    }
    
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        vector<int> path_p = getPath(root, p); //求根节点到两个节点的路径
        vector<int> path_q = getPath(root, q);
        int res;
        for(int i = 0; i < path_p.size() && i < path_q.size(); i++){ //比较两个路径，找到第一个不同的点
            if(path_p[i] == path_q[i])
                res = path_p[i]; //最后一个相同的节点就是最近公共祖先
            else
                break;
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，设共有$nn$个节点，因此最坏情况二叉搜索树变成链表，搜索到目标节点需要$O(n)O(n)$，比较路径前半段的相同也需要$O(n)O(n)$
• 空间复杂度：$O(n)O(n)$，记录路径的数组最长为$nn$

方法二：一次遍历

具体做法：

我们也可以利用二叉搜索的性质，对于某一个节点若是p与q都小于等于这个这个节点值，说明p、q都在这个节点的左子树，而最近的公共祖先也一定在这个节点的左子树；若是p与q都大于等于这个节点，说明p、q都在这个节点的右子树，而最近的公共祖先也一定在这个节点的右子树。而若是对于某个节点，p与q的值一个大于等于节点值，一个小于等于节点值，说明它们分布在该节点的两边，而这个节点就是最近的公共祖先，因此从上到下的其他祖先都将这个两个节点放到同一子树，只有最近公共祖先会将它们放入不同的子树。

class Solution {
public:
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        if(root == NULL) //空树找不到公共祖先
            return -1;
        if((p >= root->val && q <= root->val) || (p <= root->val && q >= root->val)) //pq在该节点两边说明这就是最近公共祖先
            return root->val;
        else if(p <= root->val && q <= root->val) //pq都在该节点的左边
            return lowestCommonAncestor(root->left, p, q); //进入左子树
        else //pq都在该节点的右边
            return lowestCommonAncestor(root->right, p, q); //进入右子树
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，设共有$nn$个节点，最坏情况递归遍历所有节点
• 空间复杂度：$O(n)O(n)$，递归栈深度最坏为$nn$