Pythonでn-aryツリーの直径を見つけるプログラム

仮に、n-aryツリーが与えられ、ツリーの直径を決定すると言われているとします。ツリーの直径は、ツリーの任意の2つのリーフノード間に存在する最長のパスです。木の直径を表す整数値を見つけて返す必要があります。

したがって、入力が次のような場合

その場合、出力は3になります。

このn-aryツリーの直径は、エッジ27-> 14、14-> 42、および42->56または42->65で構成されます（図では赤い線でマークされています）。パスの長さは3です。

これを解決するには、次の手順に従います-

• ans：=1

• 関数depth（）を定義します。これが定着します

  • ルートが空でない場合は、

    • 0を返す

  • 子：=値0、0を含む新しいリスト

  • temp_children：=新しいリスト

  • ルートの子の各子に対して、実行します

    • temp_childrenの最後にdepth（child）を挿入します

  • （temp_children）のサイズが0より大きい場合、

    • 子供：=temp_children

  • ans：=ansの最大値、sum（リストの子を並べ替える[（子）のインデックスの長さ-2から最後まで]）+ 1

  • 子の最大数+1を返す

• 深さ（ルート）

• return（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