题目的主要信息：

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

对于该题的最近的公共祖先定义:对于有根树T的两个结点p、q，最近公共祖先LCA(T,p,q)表示一个结点x，满足x是p和q的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先.
二叉搜索树是若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。
数据范围:3<=节点总数<=10000，0<=节点值<=10000

方法一：

首先分别找到从根节点到两个指定节点的路径。查找路径用的是findTargetNode函数，用path记录下路径，每次递归先判断root是否为NULL，如果为NULL的话表示从根节点一直到叶子结点都没有找到指定节点，当前路径行不通，需要回溯；如果root不为NULL，首先判断root是否为指定节点，如果是指定节点，说明找到了一条路径，结束递归；如果root不是指定节点，就往左右子树继续递归查找。

找到从根节点到两个指定节点的路径path1和path2后，遍历一遍两个路径，找到两个路径中的最后一个相同的节点就是他们的最近公共祖先。

具体做法：

class Solution {
public:
    void findTargetNode(TreeNode* root, vector<int>& path, int target) {
        if (!root) return;//如果root为NULL结束递归
        path.push_back(root->val);
        if (root->val == target) {
            // 找到了，结束递归
            return;
        }
        else if (root->val > target) {
            // 在左子树搜索
            findTargetNode(root->left, path, target);
            if (path.back() == target) return;
            path.pop_back();//回溯
        }
        else {
            // 在右子树搜索
            findTargetNode(root->right, path, target);
            if (path.back() == target) return;
            path.pop_back();//回溯
        }
    }

    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        vector<int> path1;
        findTargetNode(root, path1, p);//找到从root到p的路径
        vector<int> path2;
        findTargetNode(root, path2, q);//找到从root到q的路径
        int l = 0;
        while (l < path1.size() && l < path2.size() && path1[l] == path2[l]) {
            l++;
        }//找到最后一个相同节点
        return path1[l - 1];
    }
};

复杂度分析：

时间复杂度： $O (n)$ ，最坏情况下，整个树高度为n，查找节点路径需要 $O (n)$ 。
空间复杂度： $O (n)$ ，路径向量最大为n。

方法二：

采用递归。该树为二叉搜索树，所以如果r是p和q的最近公共祖先，那么p和q一定是分别在r的左右子树中，因此我们可以用这个思想进行递归。如果p和q都小于root的值，表明他们都在root的左子树中，且root不是最近公共祖先，因此往root的左子树中递归；如果p和q都大于root的值，表明他们都在root的右子树中，且root不是最近公共祖先，因此往root的右子树中递归。否则，p和q在root两边，root就是最近公共祖先。 alt 具体做法：

class Solution {
public:

    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        int v = root->val;
        if(p < v && q < v) return lowestCommonAncestor(root->left, p, q);//往左子树寻找
        if(p > v && q > v) return lowestCommonAncestor(root->right, p, q);//往右子树寻找
        return v;
    }
};

复杂度分析：

时间复杂度： $O (n)$ ，最坏情况下，整个树高度为n，两个节点为叶子结点，需要遍历整个树。
空间复杂度： $O (n)$ ，递归栈的大小为n。

题解 | #二叉搜索树的最近公共祖先#

题目的主要信息：

方法一：

方法二：