Python程序：查找N叉树的直径

假设，我们给定一个 N 叉树，并要求确定树的直径。树的直径是在树的任意两个叶子节点之间存在的路径中最长的一条。我们需要找出并返回表示树的直径的整数值。

因此，如果输入类似于

则输出将为 3。

此 N 叉树的直径由边 27->14、14->42 和 42->56 或 42->65 组成（图中用红线标记）。路径长度为 3。

为了解决这个问题，我们将遵循以下步骤：

• ans := 1

• 定义一个函数 depth()。它将接收根节点作为输入。

  • 如果根节点非空，则

    • 返回 0

  • children := 一个包含值 0、0 的新列表

  • temp_children := 一个新列表

  • 对于根节点的每个子节点，执行以下操作：

    • 将 depth(child) 插入到 temp_children 的末尾。

  • 如果 temp_children 的大小 > 0，则

    • children := temp_children

  • ans := ans、sum(对列表 children [从索引 length(children)-2 到末尾] 进行排序) + 1 的最大值

  • 返回 children 的最大值 + 1

• depth(root)

• 返回(ans -1)

示例 (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

Arnab Chakraborty

更新于: 2021年5月18日

316 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习