โปรแกรมตรวจสอบว่า Tree หนึ่งเป็น Subtree ของอีกต้น (Python)

ปัญหา

กำหนด Binary Tree 2 ต้น (root, target) ตรวจสอบว่า target เป็น subtree ของ root หรือไม่

Subtree หมายถึง: มี node ใน root ที่ subtree rooted at node นั้น identical กับ target ทุกอย่าง

วิธีแก้: Recursive Search + Match

อัลกอริทึม

1. ฟังก์ชัน solve(root, target)
2. Base cases:
   • ทั้งคู่ None → True
   • ตัวใดตัวหนึ่ง None → False
3. ถ้า root.val == target.val: เช็ค identical (solve(left,left) AND solve(right,right))
4. Else: ค้นหาต่อใน left subtree OR right subtree

โค้ด Python

class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.val = data
        self.left = left
        self.right = right

class Solution:
    def solve(self, root, target):
        if root is None and target is None:
            return True
        if root is None or target is None:
            return False
        
        if root.val == target.val:
            # ตรวจสอบ identical
            return (self.solve(root.left, target.left) and 
                    self.solve(root.right, target.right))
        else:
            # ค้นหาต่อในลูก
            return (self.solve(root.left, target) or 
                    self.solve(root.right, target))

# ทดสอบ
ob = Solution()

# Main tree
root1 = TreeNode(6)
root1.left = TreeNode(4)
root1.right = TreeNode(10)
root1.left.left = TreeNode(3)
root1.left.right = TreeNode(5)

# Target subtree
root2 = TreeNode(4)
root2.left = TreeNode(3)
root2.right = TreeNode(5)

print(ob.solve(root1, root2))  # True

# False case
root3 = TreeNode(4)
root3.left = TreeNode(3)
root3.right = TreeNode(6)  # Different
print(ob.solve(root1, root3))  # False

ความซับซ้อน

• Time: O(m × n) worst case - m nodes ใน root, n nodes ใน target
• Space: O(h) - recursion stack

Optimization: String Serialization + Substring Search

Serialize ทั้ง 2 ต้นเป็น string (preorder + markers) แล้วเช็ค substring

def serialize(self, root):
    if not root:
        return '#'
    return f'{root.val},{self.serialize(root.left)},{self.serialize(root.right)}'

def isSubtree(self, root, target):
    return self.serialize(target) in self.serialize(root)

Time: O(m + n) ด้วย KMP string matching, Space: O(m + n)

LeetCode 572: Subtree of Another Tree

โจทย์คลาสสิก - Recursive approach พอสำหรับ constraints ปกติ