牛客网：二叉搜索树的最近公共祖先

思路如下：

由于这是二叉搜索树，所以我们可以这样来想，最近的公共祖先即最近的位于p和q的值之间的节点。

两种实现方式如下

递归的写法如下：

1.若节点为空，返回-1（表示没找到）

2.若节点的值位于q和p之间，则返回该值

3.若节点的值比p和q都大，说明p，q两个节点都在当前节点的左子树，接着递归左子树

4.若节点的值比p和q都小，说明p，q两个节点都在当前节点的右子树，接着递归右子树

代码如下所示：

class Solution {
public:
    
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        if(root==NULL){
            return -1;
        }
        int val=root->val;
        if((val>=p && val<=q) || (val>=q && val<=p)){
            return val;
        }else if(val>p && val>q){
            return lowestCommonAncestor(root->left, p, q);
        }else{
            return lowestCommonAncestor(root->right, p, q);
        }
    }
};

嘛，就是直接找出从根节点到val的一条路径，一开始想用深搜啥的直接找，后面发现这是颗二叉树，利用大小关系直接找路径会快很多（只要这棵树不是单链表）

代码如下所示：

class Solution {
public:
    
    vector findPath(TreeNode *root, int k){
        vector path;
        TreeNode *node=root;
        while(node->val!=k){
            path.push_back(node->val);
            if(kval){
                node=node->left;
            }else{
                node=node->right;
            }
        }
        path.push_back(k);
        return path;
    }
    
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        vector p_path=findPath(root, p);
        vector q_path=findPath(root, q);
        int res=-1;
        for(int i=0;i