Maximum Depth of Binary Tree

Bài toán

Cho root của một cây nhị phân. Tìm độ sâu cực đại (số lượng node trên đường đi dài nhất từ gốc xuống lá).

Phân Tích & Tiếp Cận

Cách 1: Đệ quy (Recursive DFS) - Dễ nhất

Độ sâu của một Node = 1 + max(Độ sâu con trái, Độ sâu con phải). Base case: Nếu null -> Độ sâu 0.

function maxDepth(root: TreeNode | null): number {
    if (!root) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

• Time: $O(n)$.
• Space: $O(h)$.

Cách 2: Duyệt theo tầng (Iterative BFS) - Level Order Traversal

Dùng Queue. Mỗi lần duyệt hết một tầng (Level), tăng biến đếm depth lên 1.

function maxDepth(root: TreeNode | null): number {
    if (!root) return 0;

    const queue: TreeNode[] = [root];
    let depth = 0;

    while (queue.length > 0) {
        const levelSize = queue.length; // Số node ở tầng hiện tại
        depth++;

        // Xử lý hết tầng này
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift()!;
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
    }
    return depth;
}

• Lợi ích BFS: Không bị Stack Overflow nếu cây quá lệch (biến thành LinkedList). Nhưng tốn RAM để lưu hàng đợi ngang (đặc biệt cây đầy đủ).

Pattern Nhận Diện

• Tìm max/min path: Thường dùng DFS.
• Duyệt theo level: Thường dùng BFS (Queue).