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 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習