在 Python 中查找 n 元树的直径的程序

假设,我们得到一棵 n 元树,并说要确定树的直径。树的直径是树的任意两个叶节点之间存在的最长路径。我们必须找出并返回代表树直径的整数值。

所以,如果输入是这样的

那么输出将是3。

这棵 n 叉树的直径由边 27->14、14->42 和 42->56 或 42->65(在图中用红线标记)组成。路径长度为 3。

示例(Python)

让我们看看以下实现以获得更好的理解 -

class Node:
   def __init__(self, value, child = None) -> None:
     self.val= value
     self.children= []
      if child != None:
         for value in child:
            self.children.append(value)

ans = 1
def solve(root):
   def depth(root):
      global ans
      if not root:
         return 0
      children = [0, 0]
      temp_children = [depth(child) for child in root.children]
      if len(temp_children) > 0:
         children = temp_children
      ans = max(ans, sum(sorted(children)[-2:]) + 1)

      return max(children) + 1
   depth(root)

   return ans -1

node6 = Node(65)
node5 = Node(56)
node4 = Node(42, [node5, node6])
node3 = Node(32)
node2 = Node(27)
node1 = Node(14, [node2, node3, node4])
root = node1

print(solve(root))

输入

node6 = Node(65)
node5 = Node(56)
node4 = Node(42, [node5, node6])
node3 = Node(32)
node2 = Node(27)
node1 = Node(14, [node2, node3, node4])
root = node1
输出结果
3