LeetCode #226 Invert Binary Tree: สลับลูกซ้าย-ขวาแบบ recursive / BFS

โจทย์ให้พลิกต้นไม้ทวิภาค: ลูกซ้ายกับขวาของทุกโหนดสลับกัน ฟังดูง่าย แต่เป็นแบบฝึก recursion / คิวที่ดี

วิธีที่ 1: Recursive สลับแล้วเรียกลูก

สลับ left/right แล้วเรียกต่อทั้งสองด้าน เวลา O(n) พื้นที่สแตก O(h)

วิธีที่ 2: Recursive แบบสร้างโหนดใหม่

คืนโหนดใหม่จากลูกที่พลิกแล้ว ใช้เมื่อต้องการไม่แตะต้นเดิม

วิธีที่ 3: BFS ด้วยคิว (แนะนำเมื่อไม่อยากพึ่งสแตก)

ไล่ทีละชั้น สลับลูกของโหนดที่ดึงจากคิว แล้วเอาลูกเข้าคิว เวลา O(n) พื้นที่ O(w)

วิธีที่ 4: สแตกจำลอง recursion

เหมือน DFS แต่ควบคุมสแตกเอง เหมาะภาษาที่จำกัดความลึกสแตก

from __future__ import annotations

import unittest
from collections import deque


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


def invert_tree(root: TreeNode | None) -> TreeNode | None:
    if root is None:
        return None
    root.left, root.right = invert_tree(root.right), invert_tree(root.left)
    return root


def level_vals(root: TreeNode | None) -> list[int | None]:
    if root is None:
        return []
    out: list[int | None] = []
    q = deque([root])
    while q:
        node = q.popleft()
        if node is None:
            out.append(None)
            continue
        out.append(node.val)
        q.append(node.left)
        q.append(node.right)
    while out and out[-1] is None:
        out.pop()
    return out


class InvertTests(unittest.TestCase):
    def test_invert(self):
        root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7, TreeNode(6), TreeNode(9)))
        invert_tree(root)
        self.assertEqual(level_vals(root), [4, 7, 2, 9, 6, 3, 1])

    def test_empty(self):
        self.assertIsNone(invert_tree(None))


if __name__ == "__main__":
    unittest.main()

เลือกวิธีไหนดี

• สัมภาษณ์สั้น ชัด: recursive (วิธี 1)
• ต้นไม้ลึกมาก: BFS (วิธี 3)
• ต้องไม่ mutate: สร้างโหนดใหม่ (วิธี 2)

Recap

• สลับซ้าย-ขวาทุกโหนด ไม่ใช่แค่ราก
• เทสต์ต้นว่างและต้นโหนดเดียว
• เลือก recursive หรือ BFS ตามความลึกและความถนัด