Binary tree node at the longest distance

Hello everyone , I meet you again , I'm the king of the whole stack .

It's divided into two parts ：① The longest distance after root

② There is no longest distance root,

1. If the path passes through the root Root. be U and V It belongs to different subtrees , And they are the farthest nodes from the root node of the subtree . Otherwise, it is contradictory to their farthest distance . Such a situation is shown in the figure 3-13 Seen ：

2. Assume that the path does not pass Root. Then they must belong to the root K One of the subtrees .

And they are also the two farthest vertices in the subtree . Pictured 3-14 The nodes in the A：

Set the first K The two farthest nodes in the tree ：Uk and Vk, Its distance is defined as d(Uk,Vk), Then the node Uk or Vk That is, subtree K To the root node Rk The node with the longest distance . No loss of generality . We set up Uk For the subtree K Middle path root node Rk The node with the longest distance . The distance to the root node is defined as d(Uk,R). take d(Ui,R)(1<=i<=k) The two largest values in max1 and max2. Then go through the root node R The longest path of is max1+max2+2, So the tree R The distance between the two farthest points in is ：max{d(U1,V1),…, d(Uk,Vk),max1+max2+2}.

Depth first search is adopted, as shown in the figure 3-15, You only need to traverse all nodes once , The time complexity is O(|E|)=O(|V|-1), among V Is the set of points .E A collection of sides .

Copyright notice ： This article is the original article of the blogger . Blog , Do not reprint without permission .

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/117115.html Link to the original text ：https://javaforall.cn