无穷大二叉树的最近公共祖先

[题目链接](https://www.nowcoder.com/practice/7db533ff46704fd3922c1b26d2cf6fd5)

思路

有一棵无穷大的满二叉树，结点按层序从 1 开始编号。给定两个结点 $a$ 和 $b$ ，求它们的最近公共祖先（LCA）的编号。

满二叉树的性质

在按层序编号的满二叉树中，结点 $n$ 的父结点编号为 $\lfloor n / 2 \rfloor$ 。这是因为第 $k$ 层有 $2^{k-1}$ 个结点，编号从 $2^{k-1}$ 到 $2^k - 1$ ，左孩子编号为 $2n$ ，右孩子编号为 $2n+1$ 。

求 LCA 的方法

利用父结点 = $\lfloor n / 2 \rfloor$ 这一性质，不断将编号较大的结点向上移动（除以 2），直到两个结点相遇：

若 $a > b$ ，令 $a = \lfloor a / 2 \rfloor$ ；
若 $b > a$ ，令 $b = \lfloor b / 2 \rfloor$ ；
当 $a = b$ 时，即为 LCA。

这个过程的正确性在于：编号大的结点一定在更深的层或更靠右的位置，每次除以 2 就是向上走一层。两个结点最终一定会在它们的公共祖先处汇合。

样例演示

输入 $a = 2, b = 3$ ：

$b > a$ ， $b = \lfloor 3 / 2 \rfloor = 1$
$a > b$ ， $a = \lfloor 2 / 2 \rfloor = 1$
$a = b = 1$ ，输出 1

复杂度分析

时间复杂度： $O(\log \max(a, b))$ ，每次操作将较大值至少减半。
空间复杂度： $O(1)$ ，只用常数额外空间。

代码

C++
Java
Python3
JavaScript

#include <iostream>
using namespace std;
int main() {
    long long a, b;
    cin >> a >> b;
    while (a != b) {
        if (a > b) a /= 2;
        else b /= 2;
    }
    cout << a << endl;
    return 0;
}

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();
        while (a != b) {
            if (a > b) a /= 2;
            else b /= 2;
        }
        System.out.println(a);
    }
}

a, b = map(int, input().split())
while a != b:
    if a > b:
        a //= 2
    else:
        b //= 2
print(a)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
rl.on('line', function(line) {
    const [a, b] = line.trim().split(' ').map(Number);
    let x = a, y = b;
    while (x !== y) {
        if (x > y) x = Math.floor(x / 2);
        else y = Math.floor(y / 2);
    }
    console.log(x);
    rl.close();
});