バイナリサーチツリーは、各ノードが左部分木と右部分木を持つ木構造です。この問題では、与えられたバイナリサーチツリーをソートされた双方向連結リストに変換する必要があります。変換後のリストでは、各ノードの左ポインタは前のノードを指し、右ポインタは次のノードを指します。
まず、バイナリサーチツリーの中間順走査(inorder traversal)を使用して、ツリーの要素を昇順で取得します。中間順走査は、左部分木を先に探索し、次に根ノードを訪れ、最後に右部分木を探索する方法です。
アルゴリズム:
- 空の双方向連結リストを作成します。
- 中間順走査を実行して、バイナリサーチツリーの要素を昇順で取得します。
- 取得した要素を使って、双方向連結リストを構築します。各要素ごとに、前後のノードへのポインタを設定します。
コード例 (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
関数は、バイナリサーチツリーを双方向連結リストに変換するためのメインの関数です。中間順走査を実行し、双方向連結リストを構築しています。