पायथन में दिए गए बाइनरी ट्री में लिंक्ड लिस्ट मौजूद है या नहीं जांचने का प्रोग्राम

मान लीजिए हमें एक बाइनरी ट्री दी गई है जिसका रूट नोड 'root' है और एक लिंक्ड लिस्ट जिसका हेड नोड 'head' है। हमें यह ढूंढना है कि वह लिंक्ड लिस्ट उस बाइनरी ट्री में मौजूद है या नहीं। यदि ट्री में नोड्स का एक सेट एक-दूसरे से लिंक्ड लिस्ट के क्रम में जुड़ा हुआ है, और वह क्रम प्रदान की गई लिंक्ड लिस्ट के समान है, तो हम 'True' लौटाते हैं, अन्यथा 'False'।

इसलिए, यदि इनपुट है:

Tree

Linked List

तो आउटपुट True होगा।

समाधान दृष्टिकोण

• लिंक्ड लिस्ट को सरणी में बदलें
• केएमपी (KMP) एल्गोरिदम के लिए प्रीफिक्स टेबल बनाएं
• ट्री को DFS से ट्रैवर्स करते हुए KMP मिलान करें
• यदि पूरा पैटर्न मिल जाए तो True लौटाएं

उदाहरण कार्यान्वयन

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