【每日一题】Day11-1 编程题 最近公共祖先

链接：最近公共祖先__牛客网
来源：牛客网
 

[编程题]最近公共祖先

• 热度指数：10714 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 32M，其他语言64M

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

测试样例：

2，3

返回：1

根结点编号为1时，parents = child / 2

当输入的a==b直接返回a/b

找到a和b中比较大的数，一直除2直到找到a==b的情况，返回a，否则返回1

• 全部代码 

import java.util.*;

public class LCA {
    public int getLCA(int a, int b) {
        // write code here
        if(a == b){
            return b;
        }
        while(a>1 || b>1){
            if(a == b){
                return a;
            }
            if(a>b){
                a /= 2;
                continue;
            }else{
                b /= 2;
                continue;
            }
        }
        return 1;
    }
}