Question

设计一个算法,计算出给定二叉树中任意2 个结点之间的最短路径.

Answer 1

对于树中的每一个节点,维护一个dis[i],代表i节点到根节点路径长度.

写一个Lca(x,y)函数,用来返回x节点和y节点的最近公共祖先是哪一个节点.

树中最近公共祖先很很多种求法：

在信息学竞赛中一般使用的是倍增法,或者动态树.

如果你只是写一个普通的程序那么你可以朴素的取查找.当然程序会相对应的慢一点.

算法流程如下：

k=Lca(x,y);

dist=dis[x]+dis[y]-2*dis[k];//画个图就理解拉.