title: 完全二叉树的公共父结点
categories:

  • ICPC
    tags:
  • null
    abbrlink: 76dac8fe
    date: 2023-04-27 00:00:00

1.有点后序遍历的思想，就是先把左子树，右子树的结果算出来，然后合并到根节点。
2.合并时四种情况分类讨论.
3.对于遇到要找的点就可以直接返回，不管另一个点在这个点下面还是在别的子树上，都是正确的

int n, m;
int a[N];
int query(int root,int x,int y){
	//cerr<<root<<endl;
	if(root>max(x,y))return -1;
	if(root==x||root==y)return root;
	int l=query(2*root,x,y);
	int r=query(2*root+1,x,y);
	if(l==-1&&r==-1)return -1;
	if(l!=-1&&r!=-1)return root;
	if(l!=-1&&r==-1)return l;
	if(l==-1&&r!=-1)return r;
}
void solve(){
	int x,y;
	while(cin>>x>>y,x!=0){
		cout<<query(1,x,y)<<endl;
	}
	
}
int main() {
    cin.tie(0);
    
    ios::sync_with_stdio(false);

    int t;
   //cin>>t;
     t=1;
    while (t--) {
solve();
    }
    return 0;
}