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

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

तो, अगर इनपुट पसंद है

वृक्ष

लिंक्ड लिस्ट

तो आउटपुट ट्रू होगा।

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

• गिरफ्तारी:=एक नई सूची
• आकार :=गिरफ्तारी का आकार
• temp_arr :=आकार की एक सरणी (आकार + 1) -1 के साथ आरंभ की गई
• एक फंक्शन हेल्पर () को परिभाषित करें। यह जड़ लेगा, वैल
  • यदि वैल>=आकार, तो
    • सही लौटें
  • यदि रूट किसी के समान नहीं है, तो
    • झूठी वापसी
  • वैल:=वैल + 1
  • जबकि वैल> 0 और रूट का मान arr[val - 1] के समान नहीं है, do
    • वैल:=temp_arr[val - 1] + 1
  • अगर हेल्पर (रूट का बायां, वैल) या हेल्पर (रूट का दायां, वैल) सही है, तो
    • सही लौटें
  • झूठी वापसी
• शुरू करें:=सिर
• जबकि प्रारंभ शून्य के समान नहीं है, करें
  • गिरफ्तारी के अंत में प्रारंभ का मान जोड़ें
  • शुरू करें:=शुरुआत के बाद
• 1 से आकार + 1 तक के नोड के लिए, करें
  • temp_arr[नोड] :=temp_arr[नोड -1] + 1
  • जबकि temp_arr[node]> 0 और arr[node-1] arr[temp_arr[node] - 1] के समान नहीं है, do
    • temp_arr[node] :=temp_arr[temp_arr[node] - 1] + 1
• वापसी सहायक(रूट, 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