โปรแกรมเพื่อดูว่ามีรายการที่เชื่อมโยงอยู่ในต้นไม้ไบนารีที่กำหนดใน Python . หรือไม่

สมมติว่าเราได้รับไบนารีทรีที่มีโหนดรูท 'รูท' และรายการที่เชื่อมโยงที่มีส่วนหัวของโหนด 'หัว' เราต้องหาว่าลิงค์ลิสต์นั้นมีอยู่ในไบนารีทรีนั้นหรือไม่ หากชุดของโหนดในทรีมีการเชื่อมโยงซึ่งกันและกันในลำดับเป็นรายการที่เชื่อมโยง และหากลำดับนั้นคล้ายกับของรายการที่เชื่อมโยงที่ให้ไว้ เราจะส่งคืน 'จริง' หรืออย่างอื่น เราจะส่งคืน 'เท็จ'

ดังนั้นหากอินพุตเป็นแบบ

ต้นไม้

รายการที่เชื่อมโยง

แล้วผลลัพธ์จะเป็น True

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• arr :=รายการใหม่
• ขนาด :=ขนาดของ arr
• temp_arr :=อาร์เรย์ขนาด (ขนาด + 1) เริ่มต้นด้วย -1
• กำหนดฟังก์ชัน helper() สิ่งนี้จะหยั่งราก val
  • ถ้าวาล>=ขนาด แล้ว
    • คืนค่า True
  • ถ้ารูทคล้ายกับ None แล้ว
    • คืนค่าเท็จ
  • วาล :=วาล + 1
  • ในขณะที่ val> 0 และค่าของรูทไม่เหมือนกับ arr[val - 1] ให้ทำ
    • val :=temp_arr[val - 1] + 1
  • ถ้า helper(left of root, val) หรือ helper(right of root, val) เป็นจริง แล้ว
    • คืนค่า True
  • คืนค่าเท็จ
• เริ่ม :=หัว
• ในขณะที่การเริ่มต้นไม่เหมือนกับ null ให้ทำ
  • เพิ่มค่า start ต่อท้าย arr
  • เริ่ม :=ถัดไปของการเริ่มต้น
• สำหรับโหนดในช่วง 1 ถึงขนาด + 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
• return 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