AcWing 3555：二叉树（北京大学考研机试题）→公共父结点

本文介绍: 对于一个二叉树，定义当前节点的编号为 i（从 1 开始），那么它的左子节点为 2*i，右子节点是2*i+1。故寻找两个节点的公共父节点，可以让其分别除以2，直到两个节点指向同一个位置。

【题目来源】
https://www.acwing.com/problem/content/description/3435/

【题目描述】
如下图所示，由正整数 1, 2, 3, … 组成了一棵无限大的（满）二叉树。

     1
    / 
   2   3
  /  / 
 4  5 6  7
/ / / /
...     ...

从任意一个结点到根结点（编号是 1 的结点）都有一条唯一的路径，比如从 5 到根结点的路径是 (5,2,1)，从 4 到根结点的路径是 (4,2,1)，从根结点 1 到根结点的路径上只包含一个结点 1，因此路径就是 (1)。
对于两个结点 x 和 y，假设他们到根结点的路径分别是 (x1,x2,…,1) 和 (y1,y2,…,1)，那么必然存在两个正整数 i 和 j，使得从 x i 和 yj 开始，有 x i=yj,x i+1=yj+1,xi+2=yj+2,…
现在的问题就是，给定 x 和 y，要求他们的公共父结点，即 xi（也就是 yj）。

【数据范围】
1≤x, y≤2^31−1

【输入格式】
一行，两个整数，空格隔开，表示两个结点。

【输出格式】
一行，一个整数，表示公共结点。

【输入样例】
10 4

【输出样例】
2

【算法分析】
对于一个二叉树，定义当前节点的编号为 i（从 1 开始），那么它的左子节点为 2*i，右子节点是2*i+1。故寻找两个节点的公共父节点，可以让其分别除以2，直到两个节点指向同一个位置。
时间复杂度为 $O(log_2N)$ 。

【算法代码】

#include&lt;bits/stdc++.h&gt;
using namespace std;

int x,y;
int main() {
    cin&gt;&gt;x&gt;&gt;y;
    while(true) {
        if(x&gt;y) x/=2;
        else if(y&gt;x) y/=2;
        else break;
    }
    cout<<x<<endl;

    return 0;
}

/*
in:
10 4

out:
2
*/