Binary Tree & DFS — จากศูนย์จนพร้อมลุย LeetCode

จนถึงตอนนี้เราเล่นกับข้อมูลที่เรียงเป็นแถวยาว ๆ (array, string, linked list) มาตลอด หมวดนี้เราจะเจอโครงสร้างแบบใหม่ที่แตกกิ่งก้านเหมือนต้นไม้ ชื่อว่า binary tree (ต้นไม้ทวิภาค — แต่ละโหนดมีลูกได้มากสุดสองตัว) — โผล่ในโจทย์สัมภาษณ์บ่อยมาก

เครื่องมือหลักที่ใช้เดินต้นไม้คือ DFS (Depth-First Search = ค้นแบบลงลึกก่อน) ที่มักเขียนด้วย recursion (การเรียกตัวเอง) ถ้ายังไม่เคยรู้จัก tree เลยก็ไม่เป็นไร หน้านี้เริ่มจากศูนย์ จับมือสร้างต้นเล็ก ๆ แล้วค่อยไปลุยโจทย์ทีละข้อในหน้าถัดไปครับ

1. ปลดล็อกไอเดีย: จากแถวยาว → ต้นไม้กลับหัว

Array / Linked List คือ "แถวคนต่อแถว" — เดินไปข้างหน้าทีละคน Binary tree คือ "ต้นไม้กลับหัว": รากอยู่บนสุด แล้วแตกกิ่งลงล่างได้มากสุดสองทาง

• ข้อดี: แบ่งปัญหาเป็นสองต้นย่อยที่หน้าตาเหมือนกัน → ใช้ recursion (การเรียกตัวเอง) ได้พอดิบพอดี
• ข้อเสีย: ไม่มี index ให้กระโดด — ต้องเดินจาก root ลงไปทีละกิ่งเท่านั้น

2. ศัพท์ที่ต้องจำให้ขึ้นใจ

• binary tree (ต้นไม้ทวิภาค) — โครงสร้างที่แต่ละ node มีลูกได้มากสุด 2 ตัว
• root (ราก) — node บนสุด จุดเริ่มต้นของต้นไม้ทั้งต้น
• node (โหนด) — กล่องแต่ละกล่องที่เก็บค่า + ลิงก์ไปหาลูก
• left / right child (ลูกซ้าย / ลูกขวา) — มีได้ฝั่งละไม่เกินหนึ่ง
• parent (แม่) — node ที่ชี้ลงมาหา node นั้น
• leaf (ใบ) — node ที่ไม่มีลูกเลย (left และ right เป็น None)
• subtree (ต้นย่อย) — ต้นไม้ที่เริ่มจาก node ใด ๆ ลงไป
• height / depth (ความสูง / ความลึก) — จำนวนชั้นจาก root ลงไปถึง leaf ที่ไกลสุด
• traverse (เดินไล่) — การเดินผ่าน node ในต้นไม้อย่างมีระบบ
• DFS (Depth-First Search) — ค้นแบบลงลึกก่อน: เลือกกิ่งหนึ่งดิ่งลงสุดก่อน ค่อยถอยกลับมาลองกิ่งอื่น
• BFS (Breadth-First Search) — ค้นแบบกว้างก่อน: ไล่ทีละชั้นจากบนลงล่าง (เรียนหมวดถัดไป)
• recursion (การเรียกตัวเอง) — ฟังก์ชันเรียกตัวเองเพื่อแก้ปัญหาย่อยที่หน้าตาเหมือนกัน
• backtrack (ถอยกลับ) — เดินลงกิ่งหนึ่งเสร็จแล้วถอยขึ้นมา แล้วไปลองกิ่งอื่นต่อ

ลองดูรูปนี้ — root อยู่บน leaf อยู่ล่าง เส้น / กับ \ คือลิงก์จาก parent ลงไปหาลูก

          3          <- root (ชั้น 1)
         / \
        9   20         <- ชั้น 2
           /  \
          15   7       <- ชั้น 3 (9, 15, 7 เป็น leaf)

# ความสูง = 3 ชั้น
# 20 มีลูกซ้าย = 15, ลูกขวา = 7
# 9 ไม่มีลูก จึงเป็น leaf

3. [Workshop] สร้างต้นไม้ด้วยมือ (Absolute Zero)

LeetCode ให้คลาส TreeNode มาให้แล้ว — แต่เรามาประกอบต้นเล็ก ๆ ด้วยมือก่อน เพื่อให้ภาพชัด

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val      # ค่าในกล่องนี้
        self.left = left    # ลูกซ้าย (TreeNode หรือ None)
        self.right = right  # ลูกขวา (TreeNode หรือ None)

ขั้นที่ 1: ผลิตกล่องสามใบ — ตอนนี้ยังไม่เกี่ยวกัน

a = TreeNode(3)
b = TreeNode(9)
c = TreeNode(20)

ขั้นที่ 2: เกี่ยวกิ่ง — ให้ 3 เป็น root มีลูกซ้าย 9 ลูกขวา 20

a.left = b
a.right = c
# ตอนนี้: 3
#         / \
#        9   20

ขั้นที่ 3: เติมลูกให้ 20 แล้วพิสูจน์ว่าเกี่ยวกันจริง

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

root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20, TreeNode(15), TreeNode(7))

print(root.val)              # 3
print(root.left.val)         # 9
print(root.right.left.val)   # 15
print(root.right.right.val)  # 7

3
9
15
7

4. DFS คืออะไร และทำไมใช้ recursion

DFS ย่อมาจาก Depth-First Search แปลตรงตัวว่า "ค้นหาแบบลงลึกก่อน" — เลือกกิ่งหนึ่งแล้ว traverse (เดินไล่) ดิ่งลงไปให้สุดจนชน leaf แล้วค่อย backtrack (ถอยกลับ) มาลองกิ่งอื่น ต่างจาก BFS (Breadth-First Search = ค้นแบบกว้างก่อน) ที่ไล่ทีละชั้น ซึ่งเราจะเรียนหมวดถัดไป

recursion แปลว่า "การเรียกตัวเอง" — คือเขียนฟังก์ชันที่เรียกตัวเองเพื่อแก้ปัญหาย่อยที่หน้าตาเหมือนปัญหาใหญ่ ทำไม recursion เข้ากับ tree ได้พอดิบพอดี? เพราะ left child ของ node ก็คือ root ของ subtree อีกต้นหนึ่ง — ทุก node จึงเป็น "ปัญหาย่อยหน้าตาเหมือนกันเป๊ะ" เราเขียนวิธีแก้ที่ node เดียว แล้วสั่งให้เรียกตัวเองกับลูกซ้ายและลูกขวา

def dfs(node):
    if node is None:        # (1) base case: ตกขอบแล้ว — หยุดเรียกตัวเอง
        return              #     คืน 0 / None / [] แล้วแต่โจทย์

    # (2) recursive case: ถามสองต้นย่อยก่อน (เรียกตัวเอง)
    left = dfs(node.left)
    right = dfs(node.right)

    # รวม left, right กับ node.val เป็นคำตอบของต้นนี้
    return combine(node.val, left, right)

5. ลำดับการเดิน: preorder / inorder / postorder

เวลา traverse ด้วย DFS ที่แต่ละ node เราแตะ 3 อย่าง: ตัวเอง (N), ต้นย่อยซ้าย (L), ต้นย่อยขวา (R) — ลำดับที่เลือกทำมีชื่อต่างกัน แต่ทั้งหมดยังเป็น DFS (ลงลึกก่อน) เหมือนกัน

หมวดนี้ส่วนใหญ่ใช้ postorder (รอลูกเสร็จก่อนค่อยสรุป) แต่บางข้ออย่าง Count Good Nodes ใช้ top-down ที่พกข้อมูลลงไปด้วย

6. สัญญาณว่าโจทย์นี้ "เล่นกับ Tree DFS"

• โจทย์ให้ root ของ binary tree มา (หรือสองต้น)
• ถามเรื่องความลึก · เส้นทาง · ใบ · บรรพบุรุษ · นับ node ตามเงื่อนไข
• ไม่มี index ให้กระโดด — ต้อง traverse จาก root ลงไปด้วย DFS / recursion

7. สาม patterns ที่จะเจอในหมวดนี้

1. Bottom-up รวมผล — ลูกคืนคำตอบขึ้นมาก่อน แล้ว node ปัจจุบันค่อยรวม (เช่น Maximum Depth, LCA)
2. Top-down พก state — ส่งค่าที่เจอระหว่างทางลงเป็นพารามิเตอร์ของ recursion (เช่น Good Nodes, ZigZag)
3. Collect แล้วเทียบ — เก็บของที่สนใจลงลิสต์ แล้วยุบปัญหาให้เหลือเทียบลิสต์ธรรมดา (เช่น Leaf-Similar)