โปรแกรมตรวจสอบ Binary Tree สองต้นว่าเหมือนกันทุกอย่างหรือไม่ (Python)

ปัญหา

กำหนด Binary Tree 2 ต้น ตรวจสอบว่า "เหมือนกันทุกอย่าง" (Identical/Twin Trees) หมายถึง โครงสร้างเหมือนกัน และค่าในทุก node เหมือนกัน

วิธีแก้: Recursive Comparison

เปรียบเทียบ node คู่กันแบบ preorder traversal

อัลกอริทึม

1. ถ้าทั้งคู่ None → True
2. ถ้าตัวใดตัวหนึ่ง None → False
3. ถ้าค่าไม่เท่ากัน → False
4. Recursive ตรวจสอบ left subtree และ right subtree

โค้ด Python

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

class Solution:
    def solve(self, root0, root1):
        if not root0 and not root1:
            return True
        if not root0 or not root1:
            return False
        if root0.val != root1.val:
            return False
        return (self.solve(root0.left, root1.left) and 
                self.solve(root0.right, root1.right))

# ทดสอบ
ob = Solution()

# Tree 1
root1 = TreeNode(10)
root1.left = TreeNode(5)
root1.right = TreeNode(15)
root1.left.left = TreeNode(3)
root1.left.right = TreeNode(8)

# Tree 2 (เหมือนกัน)
root2 = TreeNode(10)
root2.left = TreeNode(5)
root2.right = TreeNode(15)
root2.left.left = TreeNode(3)
root2.left.right = TreeNode(8)

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

# Tree 3 (ค่าแตกต่าง)
root3 = TreeNode(10)
root3.left = TreeNode(5)
root3.right = TreeNode(15)
root3.left.left = TreeNode(3)
root3.left.right = TreeNode(9)  # 8 → 9
print(ob.solve(root1, root3))  # False

ความซับซ้อน

• Time: O(min(n,m)) - หยุดทันทีที่พบความต่าง
• Space: O(h) - recursion stack, h = ความสูงต้นไม้

Iterative Version (BFS)

from collections import deque

def solve_iterative(self, root0, root1):
    q = deque([(root0, root1)])
    while q:
        n0, n1 = q.popleft()
        if not n0 and not n1:
            continue
        if not n0 or not n1:
            return False
        if n0.val != n1.val:
            return False
        q.append((n0.left, n1.left))
        q.append((n0.right, n1.right))
    return True

Iterative version หลีกเลี่ยง recursion limit สำหรับต้นไม้ลึกมาก