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

একটি বাইনারি ট্রি দেওয়া আছে যার রুট নোড 'root' এবং একটি লিংকড লিস্ট দেওয়া আছে যার হেড নোড 'head'। সেই লিংকড লিস্টটি বাইনারি ট্রি-তে আছে কিনা তা বের করতে হবে। যদি ট্রি-তে নোডগুলোর একটি সেট পরস্পর লিংকড লিস্টের মতো অর্ডারে থাকে এবং সেই অর্ডার দেওয়া লিংকড লিস্টের সাথে মিলে, তবে 'True' রিটার্ন করব, অন্যথায় 'False'।

ইনপুট ট্রি:

Tree

Linked List

আউটপুট হবে True।

সমাধানের ধাপসমূহ

• arr := একটি নতুন লিস্ট
• size := arr-এর আকার
• temp_arr := (size + 1) আকারের -1 দিয়ে ইনিশিয়ালাইজড অ্যারে
• helper() ফাংশন সংজ্ঞায়িত করুন। এটি root, val গ্রহণ করবে:
  • যদি val >= size হয়, তবে True ফেরত দিন
  • যদি root == None হয়, তবে False ফেরত দিন
  • val := val + 1
  • যদি val > 0 এবং root.val != arr[val - 1] হয়:
    • val := temp_arr[val - 1] + 1
  • যদি helper(root.left, val) বা helper(root.right, val) True হয়, তবে True ফেরত দিন
  • False ফেরত দিন
• start := head
• যদি start != null হয়:
  • start.val কে arr-এ যোগ করুন
  • start := start.next
• node = 1 থেকে size + 1 পর্যন্ত:
  • temp_arr[node] := temp_arr[node - 1] + 1
  • যদি temp_arr[node] > 0 এবং arr[node - 1] != arr[temp_arr[node] - 1] হয়:
    • temp_arr[node] := temp_arr[temp_arr[node] - 1] + 1
• helper(root, 0) ফেরত দিন

উদাহরণ

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class ListNode:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

def insert(temp, data):
    que = []
    que.append(temp)
    while len(que):
        temp = que[0]
        que.pop(0)
        if not temp.left:
            if data is not None:
                temp.left = TreeNode(data)
            else:
                temp.left = TreeNode(0)
            break
        else:
            que.append(temp.left)
        if not temp.right:
            if data is not None:
                temp.right = TreeNode(data)
            else:
                temp.right = TreeNode(0)
            break
        else:
            que.append(temp.right)

def make_tree(elements):
    node = TreeNode(elements[0])
    for element in elements[1:]:
        insert(node, element)
    return node

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 solve(root, head):
    arr = []
    start = head
    while start:
        arr += (start.val,)
        start = start.next
    size = len(arr)
    temp_arr = [-1] * (size + 1)
    for node in range(1, size + 1):
        temp_arr[node] = temp_arr[node - 1] + 1
        while temp_arr[node] > 0 and arr[node - 1] != arr[temp_arr[node] - 1]:
            temp_arr[node] = temp_arr[temp_arr[node] - 1] + 1
    def helper(root, val):
        if val >= size:
            return True
        if not root:
            return False
        val += 1
        while val > 0 and root.val != arr[val - 1]:
            val = temp_arr[val - 1] + 1
        if helper(root.left, val) or helper(root.right, val):
            return True
        return False
    return helper(root, 0)

root = make_tree([6, 7, 8, 9, 10])
head = make_list([6, 7, 10])
print(solve(root, head))

ইনপুট

root = make_tree([6, 7, 8, 9, 10])
head = make_list([6, 7, 10])
print(solve(root, head))

আউটপুট

True