最近公共祖先
题目描述
有一棵无穷大的满二叉树，其结点按根结点一层一层地从左往右依次编号，根结点编号为1。现在有两个结点a，b。请设计一个算法，求出a和b点的最近公共祖先的编号。
给定两个int a,b。为给定结点的编号。请返回a和b的最近公共祖先的编号。注意这里结点本身也可认为是其祖先。
测试样例：
2，3
返回：1
代码如下
以下代码是讲全部的公共祖先罗列再匹配对比。
#include <stdio.h> #define MAX 100 void FindParentFuction(int num, int data[]) { int n = num; int i = 0; data[i] = n; while(n>1){ i++; n = n/2; data[i] = n; } } int main() { int i,j; int flag = 0; int nump1[MAX] = {0}; int nump2[MAX] = {0}; int num1,num2,result; scanf("%d %d",&num1,&num2); FindParentFuction(num1,nump1); FindParentFuction(num2,nump2); for(i = 0; i < MAX; i++){ for(j = 0; j < MAX; j++){ if(nump2[i] == nump1[j]){ flag = 1; result = nump1[j]; break; } } if(flag){ break; } } printf("%d\n",result); return 0; }
更加高效简洁的代码,，如此更加开源不存储数据高效实现。
int main() { int num1,num2; scanf("%d %d",&num1,&num2); while(num1!=num2){ if(num1>num2) num1/=2; else num2/=2; } printf("%d",num1); }
