โปรแกรมตรวจสอบ Tree สองต้นว่า Swap ได้กันหรือไม่ (Flip Equivalent)

ปัญหา

กำหนด Tree 2 ต้น ตรวจสอบว่า tree แรกสามารถกลายเป็น tree ที่สองได้โดยการ swap left/right children ของ node ใดๆ กี่ครั้งก็ได้ (Flip Equivalent Trees)

ตัวอย่าง: Tree1: 2→R→4→L=3,R=5 | Tree2: 2→L→4→L=3,R=5 → True (swap root's children)

วิธีแก้: BFS Level-by-Level Comparison

เปรียบเทียบแต่ละ level: ค่าต้องเหมือนกัน (หรือ reversed) และ children ต้อง match ได้

อัลกอริทึม

1. Queue 2 ตัว: que1=[root0], que2=[root1]
2. วนจน queue ว่าง:
   • ถ้าขนาด queue ต่างกัน → False
   • เก็บค่าแต่ละ level: values1, values2
   • เก็บ children สำหรับ next level: temp1, temp2 (right ก่อน left สำหรับ tree1)
   • ถ้า values1 != values2 และ values1 != reversed(values2) → False
   • que1=temp1, que2=temp2
3. จบลูป → True

โค้ด 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, root0, root1):
        que1, que2 = [root0], [root1]
        
        while que1 and que2:
            temp1, temp2 = [], []
            values1, values2 = [], []
            
            if len(que1) != len(que2):
                return False
            
            for i in range(len(que1)):
                values1.append(que1[i].val)
                values2.append(que2[i].val)
                
                # Tree1: right first (simulate flip)
                if que1[i].right:
                    temp1.append(que1[i].right)
                if que1[i].left:
                    temp1.append(que1[i].left)
                
                # Tree2: normal order
                if que2[i].right:
                    temp2.append(que2[i].right)
                if que2[i].left:
                    temp2.append(que2[i].left)
            
            if values1 != values2 and values1 != values2[::-1]:
                return False
            
            que1, que2 = temp1, temp2
        
        return True

# ทดสอบ
ob = Solution()
root = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(3)
root.right.right = TreeNode(5)

root1 = TreeNode(2)
root1.left = TreeNode(4)
root1.left.left = TreeNode(3)
root1.left.right = TreeNode(5)

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

ความซับซ้อน

• Time: O(n) - เยี่ยมทุก node
• Space: O(w) - w = max width ของ tree

Recursive Alternative

def flipEquiv(self, root1, root2):
    if not root1 and not root2:
        return True
    if not root1 or not root2:
        return False
    if root1.val != root2.val:
        return False
    # ไม่ flip หรือ flip
    return (self.flipEquiv(root1.left, root2.left) and 
            self.flipEquiv(root1.right, root2.right)) or \
           (self.flipEquiv(root1.left, root2.right) and 
            self.flipEquiv(root1.right, root2.left))

Recursive version สั้นกว่าแต่อาจ hit recursion limit

LeetCode 951: Flip Equivalent Binary Trees

นี่คือโจทย์คลาสสิก - ใช้ได้ทั้ง BFS และ Recursive