練習問題4.5順序で保存されている二叉樹の最近の公共祖先問題(浙大『データ構造』第2版)

607 ワード

転送ゲート:https://pintia.cn/problem-sets/434/problems/6180
ヒント:順番に保存された二叉樹は完全に二叉樹で、完全な二叉樹の性質を利用して問題を解いてもいいです.
ACコード:
#include
#include
using namespace std;

int n,x,y;
int a[2000];

int main(){
	cin>>n;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	scanf("%d%d",&x,&y);
	if(a[x]==0)printf("ERROR: T[%d] is NULL", x);
	else if(a[y]==0)printf("ERROR: T[%d] is NULL", y);
	else{
		while(1){
			if(x==y){
				cout<=y) x/=2;
				else y/=2;
			}
		}
	}
	return 0;
}