Chương trình tìm hiểu xem danh sách được liên kết có trong cây nhị phân nhất định bằng Python hay không

Giả sử chúng ta được cung cấp một cây nhị phân có nút gốc 'root' và danh sách liên kết có nút đầu là 'head'. Chúng ta phải tìm xem danh sách liên kết đó có tồn tại trong cây nhị phân đó hay không. Nếu một tập hợp các nút trong cây có các liên kết với nhau theo thứ tự dưới dạng danh sách được liên kết và nếu thứ tự đó tương tự với thứ tự của danh sách được liên kết đã cung cấp, thì chúng tôi trả về 'Đúng' hoặc nếu không, chúng tôi trả về 'Sai'.

Vì vậy, nếu đầu vào giống như

Cây

Danh sách được Liên kết

thì đầu ra sẽ là True.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• arr:=một danh sách mới
• size:=kích thước của arr
• temp_arr:=một mảng có kích thước (size + 1) được khởi tạo bằng -1
• Xác định một hàm trợ giúp (). Điều này sẽ có hiệu lực, val
  • if val> =size, then
    • trả về True
  • nếu root tương tự với None, thì
    • trả về Sai
  • val:=val + 1
  • while val> 0 và giá trị của root không giống với arr [val - 1], do
    • val:=temp_arr [val - 1] + 1
  • nếu helper (bên trái root, val) hoặc helper (bên phải root, val) là True, thì
    • trả về True
  • trả về Sai
• start:=head
• while start không giống với null, hãy thực hiện
  • thêm giá trị bắt đầu vào cuối arr
  • start:=tiếp theo của bắt đầu
• đối với nút trong phạm vi từ 1 đến kích thước + 1, thực hiện
  • temp_arr [node]:=temp_arr [node - 1] + 1
  • trong khi temp_arr [node]> 0 và arr [node - 1] không giống với arr [temp_arr [node] - 1], hãy thực hiện
    • temp_arr [node]:=temp_arr [temp_arr [node] - 1] + 1
• trả về trình trợ giúp (root, 0)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

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

Đầu ra

True