大家好,又见面了,我是你们的朋友全栈君。...举个例子,如下图:当u=1,v=4时,在后序遍历的过程中,访问u时,v已经被访问过了,已访问节点集合{4,7,5}的祖先节点就是1,俩者相等,所以就是集合{4,7,5}的祖先;再当u=7,v=4时,访问...如果节点v没有被访问过,那我们就不用做处理,等到下次访问到节点v时,节点u已经被处理了,按上面的方式进行理。
在实际实现的过程中,我们需要记录集合的祖先。...而跳表解法跳的时间复杂度是o(logn),因为它跳的时候是按2的次幂跳,下面详细为大家解答。...)
{
int u, v; scanf("%d%d", &u, &v);//查询u和v的LCA
printf("%d和%d的最近公共祖先为:%d\n", u, v, query(u, v));
}
return