题解 | #最近公共祖先#

最近公共祖先

最近公共祖先

/*
2022年09月21日 11:43:09
满二叉树 parent = child / 2
		1
    2       3
 4    5   6   7
 较大的数找父节点，两个数相等时，就是公共祖先
*/
class LCA {
public:
    int getLCA(int a, int b) {
        while(a != b){
            if(a > b) // 让大的数除2就是parent
                a /= 2;
            else
                b /= 2;
        }
        return a;
    }
};