首页 > 试题广场 >

二叉搜索树的最近公共祖先

[编程题]二叉搜索树的最近公共祖先
  • 热度指数：80298 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
1.对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q，最近公共祖先LCA(T,p,q)表示一个节点x，满足x是p和q的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先.
2.二叉搜索树是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值
3.所有节点的值都是唯一的。
4.p、q 为不同节点且均存在于给定的二叉搜索树中。
数据范围:
3<=节点总数<=10000
0<=节点值<=10000

如果给定以下搜索二叉树: {7,1,12,0,4,11,14,#,#,3,5}，如下图:


示例1

输入

{7,1,12,0,4,11,14,#,#,3,5},1,12

输出

7

说明

节点1 和 节点12的最近公共祖先是7
示例2

输入

{7,1,12,0,4,11,14,#,#,3,5},12,11

输出

12

说明

因为一个节点也可以是它自己的祖先.所以输出12

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
C
一个优雅的程序猿头像 一个优雅的程序猿
不看解题是想不出来，本来脑海里构思了一万行，有点怀疑就没去敲，看了解题思路，原来。。。 
int lowestCommonAncestor(struct TreeNode* root, int p, int q ) {
    if(p<root->val && q<root->val) 
        return lowestCommonAncestor(root->left, p, q);
    else if(p>root->val && q>root->val) 
        return lowestCommonAncestor(root->right, p, q);
    else 
        return root->val;
}

编辑于 2024-03-16 22:59:04 回复(0)
C
陈让然头像 陈让然 


int lowestCommonAncestor(struct TreeNode* root, int p, int q ) {
    // write code here
    //如果根节点为空
    if(!root)
    {
        return -1;
    }
    //如果根节点值等于q/p,根节点为最近公共祖先
    //对应示例二
    if(root->val==p||root->val==q)
    {
        return root->val;
    }
    //递归左子树
    int left=lowestCommonAncestor(root->left,p,q);
    //递归右子树
    int right=lowestCommonAncestor(root->right,p,q);
    //如果q/p位于根节点左右子树，根节点为最近公共祖先
    //对应示例一
    if(left!=-1&&right!=-1)
    {
        return root->val;
    }//q&p都在左子树
    else if(left!=-1)
    {
        return left;
    }//q&p都在右子树
    else 
    {
        return right;
    }
}


发表于 2023-11-21 09:13:49 回复(0)
C
小熊猫的黑眼圈头像 小熊猫的黑眼圈
int lowestCommonAncestor(struct TreeNode* root, int p, int q )
{
    // write code here
    if((p<=root->val&&q>=root->val)||(q<=root->val&&p>=root->val))
    return root->val;
    else if(p<root->val&&q<root->val)
    return lowestCommonAncestor(root->left, p, q );
    else if(p>root->val&&q>root->val)
    return lowestCommonAncestor(root->right, p, q );
    return 0;
}
发表于 2023-07-10 16:33:46 回复(0)
C
帅奶哟。头像 帅奶哟。
typedef struct TreeNode TNode;

void findPath(TNode *root, int path[], int *k, int x);

int lowestCommonAncestor(struct TreeNode* root, int p, int q ) {
    // write code here
    int path1[10000], path2[10000]; //记录路径
    int k1 = 0, k2 = 0; //记录各个数组的最大长度
    int i, j;
    int ans;    //记录最近的公共祖先

    findPath(root, path1, &k1, p);
    findPath(root, path2, &k2, q);

    for (i = 0, j = 0; i < k1 && j < k2; i++, j++){ //寻找最近公共祖先
        printf("%d %d,", path1[i], path2[j]);
        if (path1[i] == path2[j]) ans = path1[i];
    }
    return ans;

}

void findPath(TNode *root, int path[], int *k, int x){// path[]记录路径，*k记录最大长度，x为目标值
    if (root == NULL) return ;
    int i = 0;
    while(root->val != x) {
        path[i++] = root->val;  //记录路径
        if (x < root->val) root = root->left;   //目标值小于当前值，在左子树找
        // if (x > root->val) root = root->right;  为什么这一行运行会出错？
        else root = root->right;    //目标值大于当前值，在右子树找
    }
    path[i++] = root->val;  //记录目标值
    *k = i; //到达的长度
}
发表于 2023-03-16 15:41:24 回复(0)
C
椰汁giao头像 椰汁giao 
void findpath(struct TreeNode *t,int path[],int *k,int x){
    if(t==NULL)return;
    int count=0;
    while(t->val!=x){
        path[count++]=t->val;//加入路径
        if(x<t->val){//小的在左子树
            t=t->left;
        }else{//大的在右子树
            t=t->right;
        }
    }
    path[count++]=t->val;
    *k=count;
}
int lowestCommonAncestor(struct TreeNode* root, int p, int q ) {
    // write code here
    int path1[10000],path2[10000],k1=0,k2=0,ans;
    findpath(root, path1, &k1, p);//找到根到p的路径
    findpath(root, path2, &k2, q);//找到根到q的路径
    for(int i=0,j=0;i<k1&&j<k2;i++,j++){
        //最后一个相同的节点就是最近公共祖先
        if(path1[i]==path2[j]){
            ans=path1[i];
        }else{
            break;
        }
    }
    return ans;
}

发表于 2022-11-03 17:41:06 回复(0)
提交观点

问题信息

树 递归
上传者：牛客301499号
难度：
6条回答 3789浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号