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

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @param p int整型 
 * @param q int整型 
 * @return int整型
 */
int lowestCommonAncestor(struct TreeNode* root, int p, int q ) {
    // write code here
    
    if(p==q){
        return p;
    }
    int* path_p = malloc(sizeof(int)*10001);
    int* path_q = malloc(sizeof(int)*10001);
    
    int cnt_p = 0, cnt_q = 0;
    
    struct TreeNode* p_node = root;
    struct TreeNode* q_node = root;
    
    while(p_node->val != p){
        path_p[cnt_p++] = p_node->val;
        
        if(p < p_node->val){
            p_node = p_node->left;
        }else{
            p_node = p_node->right;
        }
    }
    path_p[cnt_p++] = p_node->val;
    
    while(q_node->val != q){
        path_q[cnt_q++] = q_node->val;
        if(q < q_node->val){
            q_node = q_node->left;
        }else{
            q_node = q_node->right;
        }
    }
    
    path_q[cnt_q++] = q_node->val;
    
    int ret = 0;
    
    for(int i = cnt_p-1; i >= 0; i--){
        for(int j = cnt_q-1; j >= 0; j--){
            if(path_p[i] == path_q[j]){
                ret = path_p[i];
                return ret;
            }
        }
    }
    return ret;
    
}