Pythonでソート済み連結リストから二分探索木（BST）を構築する方法

サイズ n のソート済み連結リストが与えられたとき、そのリストから二分探索木（Binary Search Tree / BST）を構築することを考えます。具体的には、k 番目に小さい値（ただし k = floor(n / 2)）をルートとし、k 番目のノードより左側にある要素から左部分木を、右側にある要素から右部分木を再帰的に構築していきます。

例えば、入力が [2, 4, 5, 7, 10, 15] の場合、出力は次のような二分探索木になります。

解法のアプローチ

この問題は、低速ポインタ（slow）と高速ポインタ（fast）を活用した「フロイドの循環検出」でもおなじみのテクニックで解くことができます。高速ポインタは1回に2つ先へ進み、低速ポインタは1つずつ進むため、高速ポインタがリストの末尾に到達したとき、低速ポインタはちょうど中央のノードを指しています。この中央ノードを BST のルートにすれば、左右の部分木はそれぞれ残りの前半・後半に対して同じ処理を再帰的に適用するだけで求められます。

手順は以下の通りです。

• solve() メソッドを定義します。引数としてノードを受け取ります。

• ノードが空（null）の場合 → None を返します。

• ノードの次が存在しない場合（要素が1つだけの場合）→ その値を持つ新しいツリーノードを返します。

• slow と fast をともに先頭ノードで初期化し、prev を None に設定します。

• fast および fast.next が存在する間、以下を繰り返します。
  prev := slow、slow := slow.next、fast := fast.next.next

• ループ終了後、prev.next を None にして、前半部分のリストを切り離します。

• 中央ノード（slow）の値を持つ新しいツリーノードをルートとします。

• ルートの左の子には solve(先頭ノード) の結果を、右の子には solve(slow.next) の結果を再帰的に代入します。

• ルートを返します。

実装例

それでは、以下のPythonコードで実際の実装を確認してみましょう。

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.data = data
        self.left = left
        self.right = right

def make_list(elements):
    head = ListNode(elements[0])
    for element in elements[1:]:
        ptr = head
        while ptr.next:
            ptr = ptr.next
        ptr.next = ListNode(element)
    return head

def print_tree(root):
    if root is not None:
        print_tree(root.left)
        print(root.data, end=', ')
        print_tree(root.right)

class Solution:
    def solve(self, node):
        if not node:
            return None
        if not node.next:
            return TreeNode(node.val)
        slow = fast = node
        prev = None
        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next
        prev.next = None
        root = TreeNode(slow.val)
        root.left = self.solve(node)
        root.right = self.solve(slow.next)
        return root

ob = Solution()
head = make_list([2, 4, 5, 7, 10, 15])
root = ob.solve(head)
print_tree(root)

入力

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

出力

2, 4, 5, 7, 10, 15,

計算量について

このアルゴリズムでは、各再帰ステップごとにリスト全体を走査して中央ノードを見つける必要があるため、時間計算量は O(n log n) になります。一方、空間計算量は再帰呼び出しによるスタックの深さ分が必要となるため、平衡な木構造の場合は O(log n) です。もし O(n) の時間計算量を目指す場合は、リストを配列に変換してインデックスでアクセスする方法や、順序付きトラバーサルを利用した構築方法も検討するとよいでしょう。