我试图找到使用递归来解决问题直径与邻接链表实现的根k元树的线性时间算法。树的直径是任何一对叶片之间的最大距离。如果我选择一个根研究（也就是，一个节点的度为> 1），它可以证明，直径是在相同的或者两片树叶之间的最大距离子树或路径的两片叶子是通过研究之间的最大距离。我的伪code这个问题：

I'm trying to find a linear-time algorithm using recursion to solve the diameter problem for a rooted k-ary tree implemented with adjacency lists. The diameter of a tree is the maximum distance between any couple of leaves. If I choose a root r (that is, a node whose degree is > 1), it can be shown that the diameter is either the maximum distance between two leaves in the same subtree or the maximum distance between two leaves of a path that go through r. My pseudocode for this problem:

Tree-Diameter(T,r)
    if degree[r] = 1 then
        height[r] = 0
        return 0
    for each v in Adj[r] do
        for i = 1 to degree[r] - 1 do
            d_i = Tree-Diameter(T,v)
    height[r] = max_{v in Adj[r]} (height[v]
    return max(d_i, max_{v in V} (height[v]) + secmax_{v in V} (height[v], 0) + 1)

要获得线性的时候，我计算的直径和每个子树的同时高度。于是，我选择的每个子树的直径和树+ 1（之间的的 secmax 功能选择高度的两个最大高度之间的最大数量[V] 和 0 ，因为一些树只能有一个孩子：在这种情况下，第二大高度 0 ）。我问你，如果该算法工作正常，如果不是，有什么问题呢？我试着概括了解决同样问题的二叉树的算法，但我不知道这是否是一个很好的概括。

To get linear time, I compute the diameter AND the height of each subtree at the same time. Then, I choose the maximum quantity between the diameters of each subtrees and the the two biggest heights of the tree + 1 (the secmax function chooses between height[v] and 0 because some subtree can have only a child: in this case, the second biggest height is 0). I ask you if this algorithm works fine and if not, what are the problems? I tried to generalize an algorithm that solve the same problem for a binary tree but I don't know if it's a good generalization.

任何帮助是AP preciated！在此先感谢！

Any help is appreciated! Thanks in advance!

推荐答案

这是一个Python实现的是什么，我相信你有兴趣在这里，一棵树被重新psented作为子树列表$ P $。

This is a python implementation of what I believe you are interested in. Here, a tree is represented as a list of child trees.

def process(tree):
  max_child_height=0
  secmax_child_height=0
  max_child_diameter=0
  for child in tree:
    child_height,child_diameter=process(child)
    if child_height>max_child_height:
      secmax_child_height=max_child_height
      max_child_height=child_height
    elif child_height>secmax_child_height:
      secmax_child_height=child_height
    if child_diameter>max_child_diameter:
      max_child_diameter=child_diameter
  height=max_child_height+1
  if len(tree)>1:
    diameter=max(max_child_diameter,max_child_height+secmax_child_height)
  else:
    diameter=max_child_diameter
  return height,diameter

def diameter(tree):
  height,diameter=process(tree)
  return diameter