当前位置：网站首页>7.19 二叉树

7.19 二叉树

2022-07-22 09:52:00 【Zhou Xuanhong】

题目链接

做题情况

7min AC

代码及题解

本题比较简单，直接观察二叉树特性就可得出。
在数据结构这门课上也学过，给一个满二叉树，就可以通过孩子的序号得到其双亲的序号，及（双亲序号=孩子序号/2）
因此本题只需要将两个孩子的序号的所有祖先写出来，然后遍历查询最近的相同的那个就可以


#include<iostream>

using namespace std;

const int N=50;
long long x,y;
long long a[N],b[N];

int main(){
    
	
	cin>>x>>y;
	
	int num1=1;
	int num2=1;
	
	a[1]=x;
	b[1]=y;
	
	while(x!=0){
    
		a[++num1]=x/2;
		x/=2;
	}
	
	while(y!=0){
    
		b[++num2]=y/2;
		y/=2;
	}
	
	for(int i=1;i<=num1;i++){
    
		for(int j=1;j<=num2;j++){
    
			if(a[i]==b[j]){
    
				cout<<a[i]<<endl;
				exit(0);
			}	
		}
	}
	return 0;
}