CC191 最近公共祖先

链接CC191 最近公共祖先

描述

将一棵无穷大满二叉树的结点按根结点一层一层地从左往右编号，根结点编号为1。现给定a，b为两个结点。设计一个算法，返回a、b最近的公共祖先的编号。注意其祖先也可能是结点本身。

分析

分析题目可知，是对满二叉树进行层序遍历，根据a,b两个节点序号，找其最近的父节点的编号。 这个问题，目前想到了两种解决方法：利用二叉堆的性质、利用位运算和二叉树性质

方法1 利用二叉堆的性质

详细思路：满二叉树的子节点与父节点之间的关系为root = child / 2 利用这个关系，如果a ！= b，就让其中的较大数除以2， 如此循环知道a == b， 此时a或b的值，即是原来两个数的最近公共祖先的序号 代码如下： class LCA {
public:
int getLCA(int a, int b) {
// write code here
while(a != b)
{
if(a > b)
a /= 2;
else
b /= 2;
}
return a;
}
};

方法2 利用位运算和二叉树性质

脑子里根据题目描述想象一颗这样的二叉树，所有的子树都是满的，从根节点出发，每层从左到右，依次给每个节点一个递增的序号。然后上面每个编号转化成二进制，就会发现，每个节点A的2个儿子节点的二进制表示，是A的二进制表示后分别追加0和1.

于是一种不需要任何数据结构的思路是，把序号从10进制数转化成二进制串，从高位到低位，找最长公共前缀，这个前缀转化成十进制int就行了。 如果二叉树向下发展，就是index2+0, index2+1,在二进制形式上就是末尾添0和1，所以有公共祖先的一定有公共子串（二进制） class LCA { public: string int2b(int x){ string ans=""; while(x){ ans=(char)((x&1)+'0')+ans; x/=2; } return ans; } int getLCA(int a, int b) { string sa=int2b(a); string sb=int2b(b); int ans=0; for(int i=0;i<sa.length()&&i<sb.length();i++){ if(sa[i]==sb[i]) ans=ans*2+(sa[i]-'0'); else break; } return ans; } };

​

总结

解决问题，要充分利用其本身的性质。