バイナリサーチツリーをソートされた双方向連結リストに変換する方法


バイナリサーチツリーは、各ノードが左部分木と右部分木を持つ木構造です。この問題では、与えられたバイナリサーチツリーをソートされた双方向連結リストに変換する必要があります。変換後のリストでは、各ノードの左ポインタは前のノードを指し、右ポインタは次のノードを指します。

まず、バイナリサーチツリーの中間順走査(inorder traversal)を使用して、ツリーの要素を昇順で取得します。中間順走査は、左部分木を先に探索し、次に根ノードを訪れ、最後に右部分木を探索する方法です。

アルゴリズム:

  1. 空の双方向連結リストを作成します。
  2. 中間順走査を実行して、バイナリサーチツリーの要素を昇順で取得します。
  3. 取得した要素を使って、双方向連結リストを構築します。各要素ごとに、前後のノードへのポインタを設定します。

コード例 (Python):

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
def binaryTreeToDoublyLinkedList(root):
    if not root:
        return None

    def inorder(node):
        nonlocal prev, head
        if not node:
            return

        inorder(node.left)

        if prev:
            prev.right = node
            node.left = prev
        else:
            head = node

        prev = node

        inorder(node.right)

    prev = None
    head = None
    inorder(root)

    head.left = prev
    prev.right = head

    return head

上記のコードでは、Nodeクラスを定義し、バイナリサーチツリーの各ノードを表現しています。binaryTreeToDoublyLinkedList関数は、バイナリサーチツリーを双方向連結リストに変換するためのメインの関数です。中間順走査を実行し、双方向連結リストを構築しています。