पायथन में लिंक की गई सूची को ज़िग-ज़ैग बाइनरी ट्री में बदलने का कार्यक्रम

मान लीजिए कि हमारे पास एक एकल लिंक की गई सूची है, हमें इसे निम्नलिखित नियमों का उपयोग करके एक बाइनरी ट्री पथ में बदलना होगा -

• लिंक की गई सूची का प्रमुख मूल है।
• प्रत्येक बाद वाला नोड माता-पिता का बायां बच्चा होता है जब उसका मान कम होता है, अन्यथा यह सही बच्चा होगा।

तो, अगर इनपुट [2,1,3,4,0,5] जैसा है, तो आउटपुट होगा

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक फ़ंक्शन को हल करें() परिभाषित करें। यह नोड लेगा
• यदि नोड शून्य है, तो
  • वापसी शून्य
• रूट:=नोड के मान के समान मान वाला ट्री नोड बनाएं
• यदि अगला नोड शून्य नहीं है, तो
  • यदि नोड के अगले का मान <नोड का मान, तो
    • रूट के बाईं ओर :=हल करें (नोड के आगे)
  • अन्यथा,
    • रूट का दायां :=हल करें (नोड के आगे)
• रिटर्न रूट

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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,