在 Python 中找出给定二叉树中是否存在链表的程序

假设我们有一个二叉树，它有一个根节点“root”和一个链表，它有一个头节点“head”。我们必须找出该链表是否存在于该二叉树中。如果树中的一组节点按链表的顺序相互链接，并且如果该顺序与提供的链表的顺序相似，则返回“True”，否则返回“False”。

所以，如果输入像

树

链表

那么输出将为真。

示例

让我们看看以下实现以更好地理解 -

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 androot.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