首页 > 试题广场 >

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

[编程题]在二叉树中找到两个节点的最近公共祖先
  • 热度指数:172853 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2,请找到 o1 和 o2 的最近公共祖先节点。

数据范围:树上节点数满足 , 节点值val满足区间 [0,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

输出

3
示例2

输入

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

输出

2

说明:本题目包含复杂数据结构TreeNode,点此查看相关信息
js最详细解释
function lowestCommonAncestor( root ,  o1 ,  o2 ) {
    // write code here
    if(!root)return null //一直遍历到最后都不存在,返回null
    if(root.val==o1 ||root.val==o2)return root.val //如果遍历时,当前节点的值和o1,o2的一个相等,返回当前节点值
   
    //从根节点开始,分别向两条路线遍历
    let left=lowestCommonAncestor(root.left,o1,o2) //向左遍历
    let right=lowestCommonAncestor(root.right,o1,o2)//向右遍历
    //以上是先序遍历,两个变量代表的值分别是:left是对当前节点整个左子树的先序遍历,right是对当前节点整个右子树的先序遍历,,,也就是说是分别是对当前节点root左右子树遍历的结果

    //上述两个遍历会从根节点开始,分别遍历到空,或者 遇到o1或o2为止。

    
    //每次遍历得到left和right的结果后,会在下面进行判断
    //如果都为null,则当前路线里没有o1和o2,都在另一条路线里
    //如果都不为null,则说明o1、o2都在当前路线,且分别在当前节点两侧,当前节点为公共祖先节点,然后一直return出去,作为最终结果;
    //如果只有一个不为null,则不为null的那一个的值  可能  为公共祖先节点(如果最开始的另一条路线全为null,则这个值就是公共祖先节点),其可能是o1或o2本身(最后一层只有一个有值,为o1或o2,然后不断return上去),也有可能是两侧分布o1、o2的公共祖先(最后一层两个变量都有值,不断return当时的节点上去的)

    if(left &&right)return root.val //在两侧,一定是公共祖先,return上去,下次走单侧,不断return至最终结果
    return left ? left :right //在某一侧,可能是传上来的两侧分布o1、o2的公共祖先,也有可能是o1或o2本身(可能是公共祖先,也有可能这一条路线只有o1、o2的其中一个,遇到了,return上去)
}


发表于 2022-10-22 11:56:14 回复(0)
function lowestCommonAncestor( root ,  o1 ,  o2 ) {
    // write code here
    if(root == null) return -1;
    if(root.val == o1 || root.val == o2) return root.val;
    let left = lowestCommonAncestor(root.left, o1,o2);
    let right = lowestCommonAncestor(root.right, o1, o2);
    if(left == -1) return right;
    if(right == -1) return left;
    return root.val;
}
module.exports = {
    lowestCommonAncestor : lowestCommonAncestor
};
发表于 2021-09-04 10:39:09 回复(0)
function lowestCommonAncestor( root ,  o1 ,  o2 ) {
    function CommmonAncestor(root,o1,o2){
        if(root==null || root.val == o1 || root.val == o2) return root;
        let left = CommmonAncestor(root.left,o1,o2);
        let right = CommmonAncestor(root.right,o1,o2);
        if(left==null){
            return right;
        }
        if(right==null){
            return left;
        }
        return root;
    }
    return CommmonAncestor(root,o1,o2).val;
}
module.exports = {
    lowestCommonAncestor : lowestCommonAncestor
};
发表于 2021-07-16 11:23:58 回复(0)