โปรแกรมตรวจสอบ Symmetric Tree (กระจก) ใน Python

ปัญหา

ตรวจสอบ Binary Tree ว่าเป็น Symmetric Tree หรือไม่ (mirror image ของตัวเอง)

Tree แรก: Symmetric | Tree ที่สอง: ไม่ Symmetric

วิธีแก้: Recursive Mirror Check

เปรียบเทียบ subtree ซ้าย-ขวา แบบ crossed

อัลกอริทึม

1. ฟังก์ชัน solve(node1, node2)
2. ทั้งคู่ None → True
3. ตัวใดตัวหนึ่ง None → False
4. ค่าไม่เท่ากัน → False
5. Recursive: solve(node1.left, node2.right) AND solve(node1.right, node2.left)

โค้ด Python

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

class Solution:
    def isSymmetric(self, root):
        return self.solve(root, root)
    
    def solve(self, node1, node2):
        if not node1 and not node2:
            return True
        if not node1 or not node2:
            return False
        return (node1.data == node2.data and 
                self.solve(node1.left, node2.right) and 
                self.solve(node1.right, node2.left))

# ทดสอบ Symmetric Tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(2)
root.left.left = TreeNode(3)
root.left.right = TreeNode(4)
root.right.left = TreeNode(4)
root.right.right = TreeNode(3)

ob = Solution()
print(ob.isSymmetric(root))  # True

# ทดสอบ Asymmetric
root2 = TreeNode(1)
root2.left = TreeNode(2)
root2.right = TreeNode(2)
root2.left.right = TreeNode(3)
root2.right.right = TreeNode(3)
print(ob.isSymmetric(root2))  # False

ความซับซ้อน

• Time: O(n) - เยี่ยมทุก node
• Space: O(h) - recursion stack

Iterative Version (BFS)

from collections import deque

def isSymmetric_iterative(self, root):
    if not root:
        return True
    q = deque([(root.left, root.right)])
    while q:
        n1, n2 = q.popleft()
        if not n1 and not n2:
            continue
        if not n1 or not n2:
            return False
        if n1.data != n2.data:
            return False
        q.append((n1.left, n2.right))
        q.append((n1.right, n2.left))
    return True

ความแตกต่างจาก Identical Trees