পাইথনে লিংকড লিস্টকে জিগ-জ্যাগ বাইনারি ট্রিতে রূপান্তর করার প্রোগ্রাম

মান লক্ষ্য করুন আমাদের কাছে একটি সিংগলি লিংকড লিস্ট আছে। আমাদের কাজ হল সেটিকে একটি বাইনারি ট্রি পাথে রূপান্তর করা নিচের নিয়ম অনুযায়ী:

• লিংকড লিস্টের হেড হবে রুট।
• পরবর্তী প্রতিটি নোড যদি প্যারেন্টের চেয়ে ছোট হয় তবে বাম চাইল্ড, অন্যথায় ডান চাইল্ড হবে।

উদাহরণস্বরূপ, যদি ইনপুট হয় [2,1,3,4,0,5], তবে আউটপুট ট্রিটি হবে নিচের ছবির মতো:

• একটি solve() ফাংশন ডিফাইন করুন যা node নেবে।
  • যদি node নাল হয়, তবে None রিটার্ন করুন।
  • root := TreeNode(node.val) বানান।
  • যদি node.next নাল না হয়, তবে:
    • যদি node.next.val < node.val হয়, তবে root.left := solve(node.next)
    • অন্যথায়, root.right := solve(node.next)
  • root রিটার্ন করুন।

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,