首页 > 试题广场 >

最近公共祖先

[编程题]最近公共祖先
  • 热度指数:12767 时间限制: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)
其实题目有意把根节点标为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)
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)
/*树的数组表示找到父亲节点是一件很容易的事情 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)
    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)
//方法一:开始看到这一题觉得递归搜索吧,这递归不好写啊,一看输入没有树,难道是找规律?画个图观察了一下,还真有规律。。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)
题目所描述的满二叉树如下:
     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)
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)

思路

满二叉树的节点与父节点的关系为:节点值/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)
#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)
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)
//一颗满树就是一个堆,因此可以使用父节点和子节点的关系
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)
如果不给你用栈这种底层为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)
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)