将一棵无穷大满二叉树的结点按根结点一层一层地从左往右编号,根结点编号为1。现给定a,b为两个结点。设计一个算法,返回a、b最近的公共祖先的编号。注意其祖先也可能是结点本身。
测试样例:
2,3
返回:1
/*树的数组表示找到父亲节点是一件很容易的事情 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; } };
//方法一:开始看到这一题觉得递归搜索吧,这递归不好写啊,一看输入没有树,难道是找规律?画个图观察了一下,还真有规律。。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); }
class LCA { public: int getLCA(int a, int b) { while(a != b){ if(a > b){ a /= 2; } else{ b /= 2; } } return a; } };
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里很高的运行排名,还是 头一回这样,纪念一下
#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)
//一颗满树就是一个堆,因此可以使用父节点和子节点的关系 class LCA { public: int getLCA(int a, int b) { while(a != b){ if(a > b) a /= 2; else b /= 2; } return a; } };
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; } };
public:
int getLCA(int a, int b) {
// write code here
while(a != b)
{
if(a > b)
a /= 2;
else
b /= 2;
}
return a;
}
};