用 Python 编写程序，用于查找给定二叉树中是否存在链表

假设我们给定一个二叉树，该二叉树有一个根节点"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 的值与 arr[val - 1] 不同，则执行
    • val := temp_arr[val - 1] + 1
  • 如果 helper(root 的左边，val) 或 helper(root 的右边，val) 为 True，则
    • 返回 True
  • 返回 False
• start := head
• 当 start 不等于 null 时，执行
  • 在 arr 末尾添加 start 的值
  • start := start 的下一个
• 对于范围为 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

相关文章

• Python 中元组列表到字典的转换
• Python - 从两个列表中配对，使得成对的元素不相同
• 使用 Python 和 SQLite 的 SQL
• 使用 pytrie 模块在 Python 中进行前缀匹配
• 创建和访问 Python 包
• 如何使用正则表达式和数据类型选择多个 DataFrame 列
• 如何在 Pandas 中查找和过滤重复行?
• 用 Python 编写程序以正确的顺序查找机场?
• 如何在 Python Pandas 中使用字典顺序切片选择数据子集?
• 用 Python 编写程序检查我们是否可以从给定的字符串字符中创建 k 个回文?

有用资源

• python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/