首页 > 试题广场 >

最近公共祖先

[编程题]最近公共祖先

热度指数：13078 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

测试样例：

2，3

返回：1

算法知识视频讲解

codermanFans

public int getLCA(int a, int b) {

int x = a > b ? b : a;

int y = a + b - x;

double h1 = Math.log((double)x) / Math.log((double) 2);

int arr [] = new int[(int)h1+1];

int count = 0;

while(x > 0){

arr[count++] = x;

x = x / 2;

}

while(y > 0){

y = y / 2;

for(int i = 0;i<h1;i++){

if(y == arr[i]){

return arr[i];

}

return 0;

}

貌似我的代码是效率最差的一个。。。。。。

发表于 2015-08-25 22:28:17 回复(0)

更多回答

推荐

九城城主

//思路：满二叉树的子节点与父节点之间的关系为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)

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

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

/*树的数组表示找到父亲节点是一件很容易的事情 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

    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

题目所描述的满二叉树如下：

/ \

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

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

#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

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

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

//一颗满树就是一个堆，因此可以使用父节点和子节点的关系
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)

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 回复(11)

纯白想念

  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)