Pythonでバイナリ検索ツリーへのリンクリストを作成するプログラム

サイズnのソートされたリンクリストノードがあるとすると、最小のk =floor（n / 2）の値をルートとして設定することにより、バイナリ検索ツリーを作成する必要があります。次に、k番目のノードの左側にあるリンクリストを使用して、左側のサブツリーを再帰的に構築します。そして、k番目のノードの右のリンクリストを使用して、右のサブツリーを再帰的に構築します。

したがって、入力が[2,4,5,7,10,15]の場合、出力は

これを解決するために、次の手順に従います-

• メソッドsolve（）を定義します。これはノードを取ります

• ノードがnullの場合、

  • nullを返す

• 次のノードがnullの場合、

  • nodeの値を持つ新しいツリーノードを返します

• 遅い：=ノード、速い：=ノード

• 前：=なし

• fastとnextoffastはnullではありませんが、実行してください

  • 前：=遅い

  • 遅い：=次の遅い

  • fast：=next of next of fast

• 前の次：=なし

• root：=値がslowの新しいツリーノード

• ルートの左側：=resolve（node）

• ルートの右：=solve（遅いの次）

• ルートを返す

理解を深めるために、次の実装を見てみましょう-

例

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,