求二叉树中节点的最长距离

分两种:①最长距离时候经过root

②最长距离不经过root,

1. 若路径经过根Root,则U和V是属于不同子树的,且它们都是该子树中道根节点最远的节点,,否则跟它们的距离最远相矛盾。这种情况如图3-13所示:

2. 如果路径不经过Root,那么它们一定属于根的K个子树之一。并且它们也是该子树中相距最远的两个顶点。如图3-14中的节点A:

设第K棵子树中相距最远的两个节点:Uk和Vk,其距离定义为d(Uk,Vk),那么节点Uk或Vk即为子树K到根节点Rk距离最长的节点。不失一般性,我们设Uk为子树K中道根节点Rk距离最长的节点,其到根节点的距离定义为d(Uk,R)。取d(Ui,R)(1<=i<=k)中最大的两个值max1和max2,那么经过根节点R的最长路径为max1+max2+2,所以树R中相距最远的两个点的距离为:max{d(U1,V1),…, d(Uk,Vk),max1+max2+2}。

采用深度优先搜索如图3-15,只需要遍历所有的节点一次,时间复杂度为O(|E|)=O(|V|-1),其中V为点的集合,E为边的集合。

不能接受失败,也意味太想去成功了,从心理学上解释,

求二叉树中节点的最长距离

相关文章:

你感兴趣的文章:

标签云: