Trong bài toán xử lý cây thư mục hoặc phân cấp dữ liệu, làm thế nào để tính chiều cao hoặc độ sâu tối đa (Maximum Depth) của một Binary Tree bằng phương pháp đệ quy và tối ưu hóa nó?

Question

Accepted Answer

Tính chiều cao hoặc độ sâu tối đa của một Binary Tree là một bài toán cơ bản nhưng cực kỳ quan trọng để đánh giá khả năng tư duy thuật toán và lập trình hướng cấu trúc của một lập trình viên cấp độ Junior.
Bản chất kỹ thuật
Chiều cao của một Binary Tree được định nghĩa là số lượng nút trên đường đi dài nhất từ nút gốc (Root) cho đến nút lá xa nhất. Tư duy giải quyết theo phương pháp chia để trị (Divide and Conquer): chiều cao của cây hiện tại sẽ bằng 1 (tính nút gốc) cộng với giá trị lớn nhất giữa chiều cao của nhánh con bên trái và nhánh con bên phải.
Giải pháp mã nguồn minh họa (Java)
public class Solution {
    public int maxDepth(TreeNode root) {
        // Điều kiện dừng (Base Case)
        if (root == null) {
            return 0;
        }

// Đệ quy tính chiều cao nhánh trái và nhánh phải
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);

// Trả về độ sâu lớn nhất cộng với 1 cho nút hiện tại
        return Math.max(leftDepth, rightDepth) + 1;
    }
}
Kinh nghiệm thực chiến Enterprise

Độ phức tạp thời gian: O(N) vì thuật toán phải duyệt qua toàn bộ N nút của cây.
Độ phức tạp không gian: O(H) với H là chiều cao của cây do việc sử dụng Stack của hệ thống để thực hiện các lời gọi hàm đệ quy.
Lưu ý quan trọng: Nếu cây bị suy biến (Skewed Tree) với số lượng bản ghi lớn (ví dụ N = 100.000), chiều cao H sẽ bằng N, dẫn đến lỗi StackOverflowError trên môi trường thực thi Java Virtual Machine (JVM). Trong trường hợp này, cần phải chuyển sang giải pháp duyệt cây không dùng đệ quy sử dụng Stack tường minh hoặc BFS kết hợp biến đếm cấp độ.

Trong bài toán xử lý cây thư mục hoặc phân cấp dữ liệu, làm thế nào để tính chiều cao hoặc độ sâu tối đa (Maximum Depth) của một Binary Tree bằng phương pháp đệ quy và tối ưu hóa nó?

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi binary tree liên quan cùng chủ đề