Pythonでn分木（n-aryツリー）のコピーを作成する方法を解説

n分木のコピーとは

本記事では、ルートノード「root」が与えられたn分木（n-aryツリー）の完全なコピーを作成し、元の木とコピーした木の両方に対して先行順走査（preorder traversal）を実行する方法を解説します。作成したコピーは、別の新しいルートノードに格納する必要があります。

使用するノードの構造は以下のとおりです。

Node:
    value : <整数>
    children : <配列>

入力例と出力例

たとえば、次のようなn分木が与えられた場合を考えてみましょう。

この場合、出力は次のようになります。

[14, 27, 32, 42, 56, 65]

木の完全なコピーが作成されているため、入力木と出力木の先行順走査の結果は同一になります。

解決手順（アルゴリズム）

この問題を解くためには、幅優先探索（BFS）を使って元の木を辿りながら、対応する新しいノードを順次生成していく方法が有効です。具体的な手順は以下のとおりです。

• rootが空であれば、そのままrootを返します。

• headとして、rootと同じ値を持つ新しいノードを作成します。

• キューqを作成し、rootとheadのペアを格納します。

• qが空になるまで、以下の処理を繰り返します。

  • qから先頭の要素を取り出し、nodeとclonedにそれぞれ代入します。

  • nodeの子ノード（chld）をすべて走査します。

  • 各子ノードについて、chldと同じ値を持つ新しいノードnew_nを作成します。

  • new_nをclonedの子リストに追加します。

  • chldとnew_nのペアをqの末尾に追加します。

• 最後にheadを返します。これがコピーされた木のルートです。

Pythonでの実装例

それでは、実際の実装を見ていきましょう。

from queue import deque
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)

def solve(root):
    if not root:
        return root
    head = Node(root.val)
    q = deque([(root, head)])
    while q:
        node, cloned = q.popleft()
        for chld in node.children:
            new_n = Node(chld.val)
            cloned.children.append(new_n)
            q.append((chld,new_n))
    return head

def treeprint(node, tree):
    if node == None:
        tree.append("None")
        return tree
    if tree == None:
        tree = []
    tree.append(node.val)
    for child in node.children:
        treeprint(child, tree)
    return tree

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

copynode = solve(root)
print(treeprint(copynode, None))

入力

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

出力

[14, 27, 32, 42, 56, 65]

まとめ

このアルゴリズムでは、deque（両端キュー）を利用したBFSによって、元の木の各ノードとコピー先のノードをペアで管理しながら処理を進めます。これにより、子ノードの数が不定であるn分木でも、効率的かつ確実に完全なコピーを作成できます。計算量はノード数をNとした場合、時間計算量・空間計算量ともにO(N)となります。