题意：
        给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。（所有节点的值都是唯一的。）


方法一：
记录路径和深度

思路：
        递归一遍二叉树，得到每个节点的父节点和深度。
        这样，就得到了p、q 不同节点到根节点的路径及长度。
        先填补路径长度差，即使得p、q 不同节点的深度相同；
        然后p、q 不同节点都循环的往前跳一格，即可得到最近公共祖先。

        

class Solution {
public:
    int dep[10005];//深度数组
    int fa[10005];//父亲数组
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        if(root){
            dep[root->val]=1;
        }
        dfs(root);//获取各节点的父节点和各节点的深度
        if(dep[p]>dep[q]){//使q的深度大于p
            swap(p,q);
        }
        int x=dep[q]-dep[p];//深度差
        while(x--){//使q的深度等于p的深度
            q=fa[q];
        }
        while(p!=q){//循环
            p=fa[p];
            q=fa[q];
        }
        return p;
        
    }
    
    void dfs(TreeNode* root){//递归
        if(!root)
            return;
        if(root->left){//递归左儿子
            fa[root->left->val]=root->val;
            dep[root->left->val]=dep[root->val]+1;
            dfs(root->left);
        }
        if(root->right){//递归右儿子
            fa[root->right->val]=root->val;
            dep[root->right->val]=dep[root->val]+1;
            dfs(root->right);
        }
    }
};


时间复杂度：
空间复杂度：


方法二：
直接递归


思路：
        
        如果节点 x 是节点 p、q 的最近公共祖先，则节点 p、q 分别一定位于节点 x 的左右子树。
        又因为是二叉搜索树，
        所以要么 p 节点的值 < x 节点的值 , x 节点的值 < q 节点的值；
        要么 q 节点的值 < x 节点的值 , x 节点的值 < p 节点的值

 

class Solution {
public:
    
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        if(root==nullptr){
            return 0;
        }
        if(p<root->val&&q<root->val){//都小于root的值，则递归左儿子节点
            return lowestCommonAncestor(root->left,p,q);
        }
        if(p>root->val&&q>root->val){//都大于root的值，则递归右儿子节点
            return lowestCommonAncestor(root->right,p,q);
        }
        return root->val;
    }
};


时间复杂度：
空间复杂度：