파이썬에서 연결 리스트를 지그재그 이진 트리로 변환하는 프로그램

단일 연결 목록이 있다고 가정하고 다음 규칙을 사용하여 이진 트리 경로로 변환해야 합니다. -

• 연결 리스트의 선두는 루트입니다.
• 각 후속 노드는 값이 더 작을 때 부모의 왼쪽 자식이고, 그렇지 않으면 오른쪽 자식이 됩니다.

따라서 입력이 [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,