【题目来源】
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，使得从 xi 和 yj 开始，有 xi=yj,xi+1=yj+1,xi+2=yj+2,…
现在的问题就是，给定 x 和 y，要求他们的公共父结点，即 xi（也就是 yj）。
【算法分析】
对于一个二叉树，定义当前节点的编号为 i（从 1 开始），那么它的左子节点为 2*i，右子节点是2*i+1。故寻找两个节点的公共父节点，可以让其分别除以2，直到两个节点指向同一个位置。
时间复杂度为。
#include<bits/stdc++.h>
using namespace std;
int x,y;
int main() {
cin>>x>>y;
while(true) {
if(x>y) x/=2;
else if(y>x) y/=2;
else break;
}
cout<<x<<endl;
return 0;
}
/*
in:
10 4
out:
2
*/【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/131620651
https://www.acwing.com/solution/content/126489/
https://www.acwing.com/solution/content/126493/
原文地址:https://blog.csdn.net/hnjzsyjyj/article/details/134688997
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.7code.cn/show_14247.html
如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！
