【Python】連結リストをジグザグ二分木に変換するプログラムの書き方

問題の概要

単方向連結リスト（片方向リンクリスト）が与えられたとき、次のルールに従って二分木へ変換することを考えます。

• 連結リストの先頭ノード（head）が、二分木のルートになります。
• それ以降の各ノードは、その値が親ノードより小さい場合は左の子に、そうでない場合は右の子になります。

たとえば、入力が [2,1,3,4,0,5] の場合、変換後の二分木は次のような「ジグザグ」形状になります。

解き方の手順

この問題は、再帰的に呼び出す関数 solve() を定義すると、シンプルに解くことができます。具体的な手順は以下の通りです。

1. ノードを引数として受け取る関数 solve() を定義します。
2. ノードが null（None）の場合は、None を返します。
3. 受け取ったノードと同じ値を持つ新しいツリーノードを作成し、これを root とします。
4. ノードの次の要素（next）が存在する場合は、値の大小によって処理を分けます。
   • next の値が現在のノードの値より小さい場合：root.left = solve(node.next) として左側に接続
   • それ以外の場合：root.right = solve(node.next) として右側に接続
5. 最後に root を返します。

Pythonでの実装例

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

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

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

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

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
        root = TreeNode(node.val)
        if node.next:
            if node.next.val < node.val:
                root.left = self.solve(node.next)
            else:
                root.right = self.solve(node.next)
        return root

ob = Solution()
L = make_list([2,1,3,4,0,5])
print_tree(ob.solve(L))

入力

[2,1,3,4,0,5]

出力

1, 3, 0, 5, 4, 2,

コードの解説と計算量

print_tree() は二分木を中順走査（In-order Traversal）で出力する関数です。「左の子 → 自分自身 → 右の子」の順に訪問するため、上記の出力では木の構造がそのまま反映されています。今回の入力では 2 → 1 → 3 → 4 → 0 → 5 の順にノードが並んでおり、値の大小比較によってすべてのノードが一方向に連なるジグザグ状の木が構築されます。

計算量については、連結リストの各ノードを一度ずつ処理するため、時間計算量は O(n) です。また、再帰呼び出しの深さがノード数に比例するため、空間計算量も再帰スタック分の O(n) となります。