Chương trình kiểm tra linked list có tồn tại trong cây nhị phân trong Python

Cho cây nhị phân (gốc root) và linked list (đầu head). Kiểm tra xem linked list có xuất hiện dưới dạng đường đi nối tiếp trong cây không (theo hướng cha→con). Trả về True/False.

Ví dụ

Cây:

    6
   / \
  7   8
 / \
9   10

Thuật toán (KMP trên cây)

Áp dụng thuật toán Knuth-Morris-Pratt (KMP) để so khớp mẫu (linked list) trên cây.

1. Chuyển linked list thành mảng arr
2. Xây dựng bảng failure function temp_arr (prefix function) của KMP
3. DFS trên cây với trạng thái val = độ dài prefix đã khớp:
   • Nếu val == len(arr) → tìm thấy, trả về True
   • Nếu nút cây None → False
   • Cập nhật val theo KMP: tăng nếu khớp, dùng failure function để lùi nếu không khớp
   • Đệ quy trái/phải với val mới

Mã nguồ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 = [temp]
    while que:
        temp = que.pop(0)
        if not temp.left:
            temp.left = TreeNode(data) if data is not None else TreeNode(0)
            break
        else:
            que.append(temp.left)
        if not temp.right:
            temp.right = TreeNode(data) if data is not None else 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.append(start.val)
        start = start.next
    size = len(arr)
    temp_arr = [-1] * (size + 1)
    
    # Xây dựng failure function (KMP prefix table)
    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))  # Output: True

Giải thích KMP trên cây

Bình thường KMP dùng cho string matching 1D. Ở đây áp dụng cho tree path matching:

• arr: pattern (linked list values)
• temp_arr: failure function, temp_arr[i] = độ dài proper prefix dài nhất của arr[:i] cũng là suffix
• DFS duy trì val = độ dài prefix đã khớp đến nút hiện tại
• Khi không khớp, dùng failure function để nhảy về prefix ngắn hơn thay vì reset về 0

Độ phức tạp: O(N + M) với N = số nút cây, M = độ dài linked list. Tối ưu hơn O(NM) naïve.