Java每日一题——最近公共祖先

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

示例1：

输入：2，3
返回：1

题目链接：

最近公共祖先__牛客网

总体而言可以分为两种情况： a为b的根节点（图中蓝色部分）；a，b为同一个根节点的孩子节点（图中绿色部分）。

首先，把ab两个值都成为a小b大，再分为两种情况递归解决问题。

import java.util.*;

public class LCA {
    
    public int getLCA(int a, int b) {
        if(a>b){//都成为a小b大
            int tmp=a;
            a=b;
            b=tmp;
        }
        if(b==2*a || b==2*a+1){//a为b的根节点
            return a;
        }
        if(a%2==0 && b==a+1){//a，b为同一个根节点的孩子节点
            return a/2;
        }
        return getLCA(a,b/2);//递归
    }
}