我要招人

去企业版

首页 > 试题广场 >

在二叉树中找到两个节点的最近公共祖先

[编程题]在二叉树中找到两个节点的最近公共祖先

热度指数：172853 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

数据范围：树上节点数满足 $1 \le n \le 10^5 \$ , 节点值val满足区间 [0,n)

要求：时间复杂度 $O(n)$

注：本题保证二叉树中每个节点的val值均不相同。

如当输入{3,5,1,6,2,0,8,#,#,7,4},5,1时，二叉树{3,5,1,6,2,0,8,#,#,7,4}如下图所示：

所以节点值为5和节点值为1的节点的最近公共祖先节点的节点值为3，所以对应的输出为3。

节点本身可以视为自己的祖先

示例1

输入

{3,5,1,6,2,0,8,#,#,7,4},5,1

输出

示例2

输入

{3,5,1,6,2,0,8,#,#,7,4},2,7

输出

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

一个优雅的程序猿

都不是编程了，感觉就是脑筋急转弯

int lowestCommonAncestor(struct TreeNode* root, int o1, int o2 ) {
    if(root==NULL)
        return -1;
    if(root->val==o1 || root->val==o2)
        return root->val;

    if(lowestCommonAncestor(root->left,o1,o2)==-1)
        return lowestCommonAncestor(root->right,o1,o2);
    if(lowestCommonAncestor(root->right,o1,o2)==-1)
        return lowestCommonAncestor(root->left,o1,o2);

    return root->val;
}

编辑于 2024-03-16 23:51:22 回复(0)

小熊猫的黑眼圈

int lowestCommonAncestor(struct TreeNode* root, int o1, int o2 )

{

// write code here

int m=-1;

int n=-1;

if(root)

{

if(root->val!=o1&&root->val!=o2)

{

m=lowestCommonAncestor(root->left, o1, o2 ) ;

n=lowestCommonAncestor(root->right, o1, o2 ) ;

if((o1==m&&o2==n)||(o2==m&&o1==n))

{

return root->val;

}

if(m==o1||m==o2)

{

return m;

}

else if(n==o1||n==o2)

{

return n;

}

else if(-1!=m&&m!=o1&&m!=o2)

{

return m;

}

else if(-1!=n&&n!=o1&&n!=o2)

{

return n;

}

return root->val;

}

return -1;

}

发表于 2023-06-28 01:07:59 回复(0)

帅奶哟。

typedef struct TreeNode TNode;

int lowestCommonAncestor(struct TreeNode* root, int o1, int o2 ) {
    // write code here
    if (root == NULL) return -1;

    if (root->val == o1 || root->val == o2) return root->val;   //返回当前节点
    //可能发生的情况：
    //左左（都在左子树）
    //右右（都在右子树）
    //左子树 右子树
    int left = lowestCommonAncestor(root->left, o1, o2);

    int right = lowestCommonAncestor(root->right, o1, o2);

    if (left == -1) {   //左左的情况未发生
        return right;
    }

    if (right == -1) {  //右右的情况未发生
        return left;
    }

    return root->val;   //那就只能发生 左子树，右子树的情况

}

发表于 2023-03-16 16:13:49 回复(0)

碧秋

为什么基本一样的代码，别人运行2ms，我却38ms，7684kB

int res;//记录遍历到最大深度时满足条件的祖先，即最近公共祖先
bool isExistPOrQ(struct TreeNode* root, int o1, int o2){//是否存在q或q结点
	if(root==NULL)//递归出口
		return false;
	bool left=isExistPOrQ(root->left,o1,o2);//因为是从叶节点往上升从而求得最大深度，所以先进行下一层递归，left表示当前root的子树中是否包含p,q结点
	bool right=isExistPOrQ(root->right,o1,o2);
	if((left&&right) || ((root->val==o1 || root->val==o2)&&(left || right)))//左右子树中存在q或p，或者当前是q或p
		res=root->val;
	return left || right || (root->val==o1 || root->val==o2);//表示子树中有P或q结点
}

int lowestCommonAncestor(struct TreeNode* root, int o1,int o2){
	isExistPOrQ(root,o1,o2);
	return res;
}

发表于 2023-03-09 11:19:04 回复(0)

五马

递归的分解思想：

typedef struct TreeNode    TreeNode;

int lowestCommonAncestor(struct TreeNode* root, int o1, int o2 ) {
    if (root == NULL)
        return -1;
    
    if (root->val == o1)
        return o1;
    else if (root->val == o2)
        return o2;
    
    int left = lowestCommonAncestor(root->left, o1, o2);
    int right = lowestCommonAncestor(root->right, o1, o2);
    
    if (left != -1 && right != -1)
        return root->val;
    else if (left == -1)
        return right;
    else if (right == -1)
        return left;
    else
        return -1;
}

发表于 2022-08-22 20:17:16 回复(0)

牛客339731127号

struct TreeNode* CommonAncestor(struct TreeNode* root, int o1, int o2) {
// write code here
if(root == NULL) return NULL;
if(root->val == o1 || root->val == o2)
return root;
struct TreeNode* left = CommonAncestor(root->left, o1, o2);
struct TreeNode* right = CommonAncestor(root->right, o1, o2);

if(left == NULL)

return right;

if(right == NULL)

return left;

return root;
}

int lowestCommonAncestor(struct TreeNode* root, int o1, int o2 ) {
// write code here
struct TreeNode* Proot = CommonAncestor(root,o1,o2);
return (Proot==NULL)?-1:Proot->val;

}

发表于 2022-04-11 22:35:21 回复(0)