Pythonで二分探索木をレベル順（幅優先）走査によりリンクリストへ変換するプログラム

二分探索木が与えられたとき、レベル順走査（幅優先走査：BFS）を用いて、それを単方向リンクリストへ変換することを考えます。木の各ノードの値を、上の階層から左から右の順にたどりながら、連結リストとしてつなげていくイメージです。

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

この場合、出力は [5, 4, 10, 2, 7, 15] となります。

解法のアプローチ

この問題は、キュー（待ち行列）を使った典型的な幅優先探索のパターンで解くことができます。手順は以下の通りです。

• head := ダミー用の新しいリンクリストノードを作成

• currNode := head（現在の追加位置を指すポインタ）

• q := ルートノードを格納したキューを用意

• キュー q が空になるまで、以下を繰り返します。

  • curr := キューの先頭要素を取り出す

  • curr が null でない場合：

    • currNode の next に、curr の値を持つ新しいリンクリストノードを設定

    • currNode をその新しいノードへ進める

    • curr の左の子をキューの末尾に追加

    • curr の右の子をキューの末尾に追加

• 最後に、head の next（ダミーノードを除いた先頭）を返す

ポイントは、ダミーのヘッドノードを用意しておくことで、リストへの追加処理をシンプルに記述できる点です。また、null の子もキューに入れることで、木の構造を崩さずにレベル順の並びを保てます。

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

実装例

class ListNode:
    def __init__(self, data, next = None):
        self.val = data
        self.next = next

class TreeNode:
    def __init__(self, data, left = None, right = None):
        self.val = data
        self.left = left
        self.right = right

def print_list(head):
    ptr = head
    print('[', end = "")
    while ptr:
        print(ptr.val, end = ", ")
        ptr = ptr.next
    print(']')

class Solution:
    def solve(self, root):
        head = ListNode(None)   # ダミーノード
        currNode = head
        q = [root]
        while q:
            curr = q.pop(0)
            if curr:
                currNode.next = ListNode(curr.val)
                currNode = currNode.next
                q.append(curr.left)
                q.append(curr.right)
        return head.next

ob = Solution()
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(10)
root.left.left = TreeNode(2)
root.right.left = TreeNode(7)
root.right.right = TreeNode(15)
head = ob.solve(root)
print_list(head)

入力

root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(10)
root.left.left = TreeNode(2)
root.right.left = TreeNode(7)
root.right.right = TreeNode(15)
head = ob.solve(root)

出力

[5, 4, 10, 2, 7, 15]

計算量について

このアルゴリズムでは、各ノードをちょうど1回ずつ訪問するため、時間計算量は O(N)（N はノード数）です。一方、キューには最大で木の最下層のノード数が保存されるため、空間計算量も最悪ケースで O(N) となります。

なお、list.pop(0) は先頭要素の削除に O(N) のコストがかかるため、大規模な木を扱う場合は collections.deque の popleft() を使うと、先頭からの取り出しが O(1) になり、より効率的です。