โปรแกรมตรวจสอบ Linked List อยู่ใน Binary Tree หรือไม่ใน Python

กำหนด Binary Tree (รูท root) และ Linked List (หัว head) ต้องการตรวจสอบว่า Linked List มีอยู่ใน Binary Tree หรือไม่ หากมีชุดโหนดในต้นไม้ที่เชื่อมต่อกันตามลำดับเหมือน Linked List คืนค่า True มิฉะนั้น False

ตัวอย่าง

Tree:

Linked List:

ผลลัพธ์: True (พบเส้นทาง 6 → 7 → 10 ในต้นไม้)

วิธีแก้ปัญหา

1. แปลง Linked List เป็นอาร์เรย์ arr
2. สร้าง temp_arr (KMP failure function) สำหรับ pattern matching
3. ใช้ DFS บนต้นไม้ พร้อมติดตามความคืบหน้าการ match (val)
4. เมื่อ val >= len(arr) หมายถึง match ครบแล้ว คืนค่า True
5. ใช้ KMP logic ข้ามการ match ที่ล้มเหลวได้อย่างมีประสิทธิภาพ

ตัวอย่างโค้ด

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

อินพุต / เอาต์พุต

Input:  root = make_tree([6, 7, 8, 9, 10]), head = make_list([6, 7, 10])
Output: True

หลักการ: ใช้ KMP (Knuth-Morris-Pratt) algorithm ร่วมกับ DFS บนต้นไม้ เพื่อหา pattern (linked list) ใน path ของต้นไม้ได้ในเวลา O(n + m) โดย n = จำนวนโหนดต้นไม้, m = ความยาว linked list