最近公共祖先 牛客网 程序员面试金典 C++ Python
题目描述
有一棵无穷大的满二叉树，其结点按根结点一层一层地从左往右依次编号，根结点编号为1。现在有两个结点a，b。请设计一个算法，求出a和b点的最近公共祖先的编号。
给定两个int a,b。为给定结点的编号。请返回a和b的最近公共祖先的编号。注意这里结点本身也可认为是其祖先。
测试样例：
2，3
返回：1
C++
class LCA { public: //run:2ms memeory:468k int getLCA(int a, int b) { while(a != b){ if (a>b) a /=2; if (b>a) b /=2; } return a; } };Python
class LCA: #run:22ms memory:5732k def getLCA(self, a, b): while a!=b: if a>b: a /=2 if a<b: b /=2 return a
转载于:https://www.cnblogs.com/vercont/p/10210316.html
相关资源：JAVA上百实例源码以及开源项目