首页 > 试题广场 >

最近公共祖先

[编程题]最近公共祖先
  • 热度指数：12595 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

将一棵无穷大满二叉树的结点按根结点一层一层地从左往右编号，根结点编号为1。现给定a，b为两个结点。设计一个算法，返回a、b最近的公共祖先的编号。注意其祖先也可能是结点本身。

测试样例： 
2，3
返回：1
算法知识视频讲解
查看答案及解析
添加回答
推荐
九城城主头像 九城城主
//思路：满二叉树的子节点与父节点之间的关系为root = child / 2
//利用这个关系，如果a ！= b，就让其中的较大数除以2， 如此循环知道a == b，
//即是原来两个数的最近公共祖先
//代码如下：
 class LCA {
public:
    int getLCA(int a, int b) {
        // write code here
        while(a != b)
            {
            if(a > b)
                a /= 2;
            else
                b /= 2;
        }
        return a;
    }
};
编辑于 2015-08-17 19:01:23 回复(34)
toraoh头像 toraoh
如果不给你用栈这种底层为deque这种慢的像蜗牛爬一样的容器类怎么办？

脑子里想想这样的二叉树，然后上面每个编号转化成二进制，于是发现，每个节点A的2个儿子节点的二进制表示，是A的二进制表示后分别追加0和1.

于是一种不需要任何数据结构的思路是，把10进制数转化成二进制串，从高位到低位，找最长公共前缀，这个前缀转化成十进制int就行了。 

class LCA {
public:
    string int2b(int x){
        string ans="";
        while(x){
            ans=(char)((x&1)+'0')+ans;
            x/=2;
        }
        return ans;
    }
    int getLCA(int a, int b) {
        string sa=int2b(a);
		string sb=int2b(b);
        int ans=0;
        for(int i=0;i<sa.length()&&i<sb.length();i++){
			if(sa[i]==sb[i]) ans=ans*2+(sa[i]-'0');
			else break;
		}
        return ans;
    }
};

发表于 2015-08-12 19:48:39 回复(10)
NioNv头像 NioNv
其实题目有意把根节点标为1，已经有点简化啦，这个时候node_father = node_child / 2。所以实现起来很简单。
class LCA {
public:
    int getLCA(int a, int b) {
        // write code here
        if (a == b)
            return a;
        return a>b? getLCA(a/2, b): getLCA(a, b/2);
    }
};
编辑于 2016-06-01 09:01:14 回复(1)
C/C++
牛客7311123头像 牛客7311123
int getLCA(int a, int b) {
        while(a!=b){
            while(a>b) a/=2;
            while(a<b) b/=2;
        }
        return a;
    }
发表于 2017-08-25 13:25:40 回复(0)
540485909头像 540485909 
/*树的数组表示找到父亲节点是一件很容易的事情 parent = child / 2*/
class LCA {
public:
	int getLCA(int a, int b) {
		vector<int> patha;
		vector<int> pathb;
		patha.push_back(a);
		pathb.push_back(b);
		/*找到从根节点到 a 节点所经过的路径 */
		while (a >= 1)
		{
			patha.push_back(a / 2);
			a = a / 2;
		}
		/* 找到从根节点到 b 节点所经过的路径*/
		while (b >= 1)
		{
			pathb.push_back(b / 2);
			b = b / 2;
		}
		int i = patha.size() - 1;
		int j = pathb.size() - 1;
		/* 两个数组中从数组的后面 找到 第一次出现相同的数据 比如 [1,3,5,7][1,3，5,7,8] 7*/
		while (i >= 0 && j >= 0)
		{
			if (patha[i] == pathb[j])
			{
				i--;
				j--;
			}
			else
			{
				return patha[++i];
			}
		}
		return 1;
	}
};

发表于 2016-08-20 22:06:25 回复(0)
Aurora1头像 Aurora1 
    public int getLCA(int a, int b) {
		while (a != b) {
			for (; a > b; a/=2);
			for (; a < b; b/=2);
		}
		
		return a;
	}

发表于 2016-04-08 15:56:56 回复(0)
请继续，○◇头像 请继续，○◇
import java.util.*;

public class LCA {
    public int getLCA(int a, int b) {
        // write code here
        while(a!=b){
            if(a>b) a/=2;
            else    b/=2;
        }
        return a;
    }
}
发表于 2018-04-02 10:46:53 回复(0)
Java
村长，那人偷牛！头像 村长，那人偷牛！ 
//方法一：开始看到这一题觉得递归搜索吧，这递归不好写啊，一看输入没有树，难道是找规律？画个图观察了一下，还真有规律。。QAQ，我是菜鸟我怕谁
public int getLCA(int a, int b) {
        if(a==b) return a;
        while(a!=b){
            a=a>b?a>>1:a;
            b=b>a?b>>1:b;
        }
        return a;
    }
//方法二：最近在学习递归，所以。。。。
 public int getLCA(int a, int b) {
        return a==b?b:a>b?getLCA(a>>1,b):getLCA(a,b>>1);
    }

编辑于 2017-05-13 17:11:00 回复(1)
C/C++
WZ_Dale头像 WZ_Dale
题目所描述的满二叉树如下：
     1 
     / \ 
    2 3 
   / \  / \ 
 4 5 6 7 
上述树中子节点与父节点之间的关系为root = child / 2
所以如果a ！= b，就让其中的较大数除以2， 如此循环直到a == b 即是原来两个数的最近公共祖先
比如： 2和7的最近公共祖先：7/2 = 3 ---> 3/2 = 1， 2/2 = 1， 得到1为它们的公共祖先题目ID：36910-求最大连续bit数 
class LCA {
public:
    int getLCA(int a, int b) {
       while(a != b){
           if(a > b){
               a /= 2;
           }
           else{
               b /= 2;
           }
       }
        return a;
    }
};
发表于 2020-06-07 20:14:26 回复(0)
木然猫猫头像 木然猫猫
利用完全二叉树的性质。编号为x的节点的父节点为x/2 

class LCA {
public:
    int getLCA(int a, int b) {
        while (a != b) {
            if (a > b)
                a /= 2;
            else
                b /= 2;
        }
        return a;
    }
};

运行时间：4ms

占用内存：480k


发表于 2018-12-26 00:23:01 回复(0)
此广告位出租头像 此广告位出租
不断的寻找a,b的父结点，一旦有相同的就为结果返回 
public class LCA {
    public int getLCA(int a, int b) {
        // write code here
        if (a == b)
			 return a;
		 while (a >=1 && b >=1){
			 if (a == b){
				 return a;
			 }
			 if (a > b){
				 a /= 2;
				 continue;
			 }
			 if (a < b){
				 b /= 2;
				 continue;
			 }			 
		 }
		 return 1;	
    }
}
不过很意外，得到了一个java里很高的运行排名，还是 头一回这样，纪念一下
发表于 2017-07-31 16:29:11 回复(0)
妇科圣手头像 妇科圣手 
import java.util.*;

public class LCA {
    public int getLCA(int a, int b) {
        // write code here
        // 第一反应就应该是个数学问题
        // 根节点为1，父节点为子节点/2
        while (a != b) {
            if (a > b)
                a >>= 1;
            else 
               b >>= 1;
        }
        return a;
    }
}
34ms
583k
编辑于 2017-06-04 21:46:26 回复(0)
maoxiaomi头像 maoxiaomi 
public int getLCA(int a, int b) {
        // write code here
        // parent=child/2;
        while(a!=b){
           if(a>b) a=a/2;
           else b=b/2;    
       }
       return a;
    }

发表于 2017-04-30 16:13:07 回复(0)
Java
大闲人柴毛毛头像 大闲人柴毛毛

思路

满二叉树的节点与父节点的关系为：节点值/2=父节点值。 因此： 当a!=b的时候就一直循环，将大的那个除以2，再比较是否相同，直到相同为止。

public int getLCA(int a, int b) {
    while ( a>=1 && b>=1 && a!=b ) {
        if ( a>b ) {
            a /= 2;
        }
        else {
            b /= 2;
        }
        if ( a==b ) {
            return a;
        }
    }
    return 0;
}
发表于 2017-03-31 11:30:59 回复(0)
夜小楼Dream头像 夜小楼Dream 
#Python 版 
把其祖先保存下来，然后比较
# -*- coding:utf-8 -*-
class LCA:
    def getLCA(self, a, b):
        # write code here
        if a == b:
            return a
        ap = [a]
        while a !=1:
            ap.append(a/2)
            a/=2
        bp = [b]
        while b!=1:
            bp.append(b/2)
            b/=2
        lensa= len(ap)-1
        lensb = len(bp)-1
        while lensa>=0 and lensb>=0:
            if ap[lensa] == bp[lensb]:
                lensa-=1
                lensb-=1
            else:
                return ap[lensa+1]
        if lensa==-1:
            return ap[0]
        if lensb ==-1:
            return bp[0]

print LCA().getLCA(2,4)

#参考 面试金典 更简单的方式
# -*- coding:utf-8 -*-
class LCA:
    def getLCA(self, a, b):
        # write code here
        while a!=b:
            if a>b:
                a/=2
            elif a<b:
                b/=2
            else:
                break
        return a

print LCA().getLCA(2,4)
编辑于 2017-02-10 19:17:37 回复(0)
AKG头像 AKG 
public class LCA {


public int getLCA(int a, int b) {
while(a!=b){int c=a>b?(a>>=1):(b>>=1);}
return a;}}
编辑于 2016-09-07 23:53:05 回复(0)
Java
蓝胖子SHD头像 蓝胖子SHD
public int getLCA(int a, int b) {
        while(a!=b){
                while(a>b)a=a>>1;
                while(a<b)b=b>>1;
        }
        return a;
}
编辑于 2016-08-12 14:33:17 回复(0)
丷柠檬头像 丷柠檬
public class LCA {
    public int getLCA(int a, int b) {
        // write code here
        if(a<b)
            return getLCA(a,b/2);
        if(a==b)
            return a;
        return getLCA(a/2,b);
    } 
}

发表于 2016-07-01 23:18:41 回复(0)
MichaelTim头像 MichaelTim 
//一颗满树就是一个堆，因此可以使用父节点和子节点的关系
class LCA {
public:
    int getLCA(int a, int b) {
        while(a != b){
            if(a > b) a /= 2;
            else b /= 2;
        }
        return a;
    }
};

发表于 2016-05-27 14:43:08 回复(0)
纯白想念头像 纯白想念
classLCA {
public:
    intgetLCA(inta, intb) {
        // write code here
        while(a!=b){
            if(a>b) a/=2;
            elseb/=2;
        }
        returna;
    }
};//乱写的
编辑于 2015-09-29 17:47:17 回复(0)
C/C++
头包咕头像 头包咕 
class LCA {
public:
    int getLCA(int a, int b) {
        // write code here
        if(a == b)  return a;

        int m = max(a, b);

        return getLCA(m/2, m == a ? b : a);

    }
};

发表于 2023-07-24 16:46:36 回复(0)
提交观点

问题信息

动态规划 递归
难度：
110条回答 28771浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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