algorithm - 根Kary树的直径

我试图找到一个线性时间算法，使用递归来解决用邻接列表实现的有根k元树的直径问题。树的直径是任何一对树叶之间的最大距离。如果我选择一个根 >（即，一个节点的度为> 1），可以显示直径是同一子树中两个叶子之间的最大距离，或者是路径的两个叶子之间的最大距离。我这个问题的伪代码：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个函数在cc和cc之间选择，因为一些子树只能有一个子体：在这种情况下，第二大的高度是r）。我问你这个算法是否运行良好，如果不是，有什么问题？我试着推广一个算法来解决二叉树的相同问题，但我不知道它是否是一个很好的推广。感谢您的帮助！提前谢谢！ 最佳答案 这是一个python实现，我相信您对它感兴趣。在这里，树被表示为子树的列表。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,diameterdef diameter(tree): height,diameter=process(tree) return diameter关于algorithm - 根Kary树的直径，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9698344/