Pythonでリンクリストをジグザグ二分木に変換するプログラム

単一リンクリストがあるとすると、次のルールを使用してそれをバイナリツリーパスに変換する必要があります-

• リンクリストの先頭はルートです。
• 後続の各ノードは、値が小さい場合は親の左の子になり、それ以外の場合は右の子になります。

したがって、入力が[2,1,3,4,0,5]の場合、出力は

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

• 関数solve（）を定義します。これはノードを取ります
• ノードがnullの場合、
  • nullを返す
• root：=ノードの値と同じ値のツリーノードを作成します
• 次のノードがnullでない場合、
  • ノードの次の値<ノードの値の場合、
    • ルートの左側：=solve（ノードの次）
  • それ以外の場合、
    • ルートの権利：=solve（ノードの次）
• ルートを返す

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

例

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,