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

保存路径法

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @param p int整型 
 * @param q int整型 
 * @return int整型
 */
 #define Maxsize 20
struct TreeNode** getpath(struct TreeNode* p,int target,int* count){
    struct  TreeNode** path = (struct TreeNode**)malloc(sizeof(struct TreeNode*)*Maxsize);
    int j = 0;
    for(int i = 0;i<Maxsize;i++){
        path[i] = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    }
    while(p->val!=target){
        path[j] = p;
        if(p->val<target) p = p->right;
        else p = p->left;
        j++;
    }
    path[j] = p;
    *count = j;
    return path;
}
int lowestCommonAncestor(struct TreeNode* root, int p, int q ) {
    // write code here
    int count1 = 0;
    int count2 = 0;
    struct TreeNode** path1 = getpath(root,p,&count1);
    struct TreeNode** path2 = getpath(root,q,&count2);
    int resul;
    for(int i = 0;i<=count1&&i<=count2;i++){
        if(path1[i]->val == path2[i]->val)
            resul = path1[i]->val;
        else break;
    }
    return resul;
}