LeetCode #104 Maximum Depth: Recursive DFS, stack หรือ BFS เลือกจากรูปทรงต้นไม้

Maximum Depth of Binary Tree ถามจำนวน node บนเส้นทางยาวที่สุดจาก root ถึง leaf ต้นไม้ว่างมีความลึก 0 ส่วนต้นไม้ที่มี root ตัวเดียวลึก 1 นิยามสองข้อนี้ควรพูดก่อนเขียนโค้ด เพราะช่วยกัน off-by-one ได้แทบทั้งหมดครับ

วิธี 1: Recursive DFS

ใช้สมการ depth(node) = 1 + max(depth(left), depth(right)) และให้ None คืน 0 เวลา O(n) เพราะเยี่ยมทุก node พื้นที่ call stack O(h) เมื่อ h คือความสูง อ่านใกล้คำนิยามที่สุดและเป็น default ที่ดีถ้าต้นไม้ไม่ลึกเกิน recursion limit

วิธี 2: Iterative DFS พร้อม stack

เก็บคู่ (node, depth) แล้วอัปเดตค่าสูงสุด ใช้เวลา O(n) และพื้นที่ O(h) โดยประมาณสำหรับต้นไม้สมดุล แต่ไม่เสี่ยง RecursionError กับต้นไม้เอียงยาว จึงเหมาะกับ input ที่รูปทรงควบคุมไม่ได้

วิธี 3: BFS ทีละระดับ

queue เก็บ node ทั้ง level เดียวกัน เพิ่ม depth หลังประมวลผลครบชั้น ใช้เวลา O(n) และพื้นที่ O(w) เมื่อ w คือความกว้างสูงสุด ตรงกับโจทย์ “นับระดับ” มาก แต่ต้นไม้กว้างมากอาจใช้ memory สูงกว่า DFS

from collections import deque
from dataclasses import dataclass
import unittest


@dataclass
class TreeNode:
    value: int
    left: "TreeNode | None" = None
    right: "TreeNode | None" = None


def recursive(root: TreeNode | None) -> int:
    if root is None:
        return 0
    return 1 + max(recursive(root.left), recursive(root.right))


def iterative_dfs(root: TreeNode | None) -> int:
    if root is None:
        return 0
    best, stack = 0, [(root, 1)]
    while stack:
        node, depth = stack.pop()
        best = max(best, depth)
        if node.left:
            stack.append((node.left, depth + 1))
        if node.right:
            stack.append((node.right, depth + 1))
    return best


def bfs(root: TreeNode | None) -> int:
    if root is None:
        return 0
    depth, queue = 0, deque([root])
    while queue:
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        depth += 1
    return depth


class MaximumDepthTests(unittest.TestCase):
    def test_all_methods(self):
        root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
        skewed = TreeNode(1, right=TreeNode(2, right=TreeNode(3)))
        for solve in (recursive, iterative_dfs, bfs):
            self.assertEqual(solve(root), 3)
            self.assertEqual(solve(skewed), 3)
            self.assertEqual(solve(None), 0)


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

Decision table

วิธี	เวลา	พื้นที่	จุดเสี่ยง	แนะนำเมื่อ
Recursive DFS	O(n)	O(h) stack	recursion limit	tree มีขอบเขตความลึกและต้องการโค้ดชัด
Iterative DFS	O(n)	O(h) โดยทั่วไป	ต้องถือ depth เอง	tree อาจเอียงหรือลึกมาก
BFS	O(n)	O(w)	queue ใหญ่ใน tree กว้าง	ต้องทำงานระดับต่อระดับอยู่แล้ว

Edge cases และคำแนะนำ

เทสต์ tree ว่าง, node เดียว, skewed ทั้งซ้าย/ขวา และ tree กว้างที่หลาย node มีลูกไม่ครบ อย่าสับสน maximum depth กับจำนวน edge: LeetCode ข้อนี้นับ node ดังนั้น root เดี่ยวตอบ 1 หาก production tree อาจมี cycle หรือ node ถูกแชร์ มันไม่ใช่ tree ตามสัญญาอีกแล้ว ต้องมี visited set หรือ validation เพิ่ม

ในการสัมภาษณ์เริ่ม recursive DFS เพราะพิสูจน์ง่าย แล้วกล่าวข้อจำกัด stack พร้อมเสนอ iterative DFS สำหรับ input ที่ไม่รับประกันความลึก BFS ควรเลือกเมื่อขั้นต่อไปต้องใช้ level order อยู่แล้ว ไม่ใช่เพียงเพราะ queue ดูคุ้นกว่า

Recap

• base case None = 0 ทำให้ node เดี่ยวได้ depth 1 อัตโนมัติ
• ทุกวิธีใช้เวลา O(n) แต่พื้นที่ขึ้นกับความสูงหรือความกว้าง
• recursive DFS ชัดที่สุด; iterative DFS ทนต้นไม้ลึก; BFS เหมาะงานเป็นระดับ
• ระบุว่านับ node ไม่ใช่ edge ก่อนเริ่มครับ