Làm thế nào để đếm tổng số nút (Count Nodes) và tổng số lá (Count Leaf Nodes) trong một Cây nhị phân sử dụng phương pháp đệ quy?

Question

Accepted Answer

Bản chất cơ chế hoạt động
Bài toán xử lý trên cây thường rất phù hợp với tư duy chia để trị (Divide and Conquer) thông qua phương pháp đệ quy. Để giải quyết bài toán đếm nút và đếm lá, chúng ta định nghĩa bài toán lớn thành các bài toán con trên các cây con trái và cây con phải.
Thuật toán chi tiết

Đếm tổng số nút (Count Total Nodes):

Điều kiện dừng (Base case): Nếu nút hiện tại là null, trả về 0.
Bước đệ quy: Tổng số nút = 1 (nút hiện tại) + số nút ở cây con trái + số nút ở cây con phải.

Đếm tổng số lá (Count Leaf Nodes):

Lá là nút không có nút con trái và nút con phải (left === null && right === null).
Điều kiện dừng 1: Nếu nút hiện tại là null, trả về 0.
Điều kiện dừng 2: Nếu nút hiện tại là nút lá, trả về 1.
Bước đệ quy: Tổng số lá = số lá ở cây con trái + số lá ở cây con phải.

Ví dụ mã nguồn minh họa bằng JavaScript
// Đếm tổng số nút
function countNodes(root) {
    if (root === null) {
        return 0;
    }
    return 1 + countNodes(root.left) + countNodes(root.right);
}

// Đếm tổng số nút lá
function countLeafNodes(root) {
    if (root === null) {
        return 0;
    }
    if (root.left === null && root.right === null) {
        return 1;
    }
    return countLeafNodes(root.left) + countLeafNodes(root.right);
}
Độ phức tạp

Độ phức tạp thời gian (Time Complexity): O(N) vì thuật toán phải thăm mỗi nút trên cây đúng một lần.
Độ phức tạp không gian (Space Complexity): O(H) với H là chiều cao của cây, tương ứng với dung lượng bộ nhớ tiêu thụ của Call Stack trong quá trình gọi đệ quy. Trường hợp xấu nhất (cây suy biến), độ phức tạp không gian là O(N).

Kinh nghiệm thực chiến cho Junior

Khi viết đệ quy, luôn phải đặt Base case (điều kiện dừng) lên hàng đầu để tránh lỗi tràn bộ nhớ Stack Overflow.
Trong các ứng dụng doanh nghiệp, nếu cây có kích thước quá lớn (hàng triệu nút), việc dùng đệ quy sâu có thể gây crash ứng dụng, lúc này nên chuyển sang dùng thuật toán khử đệ quy (Iterative) kết hợp Stack thủ công.

Làm thế nào để đếm tổng số nút (Count Nodes) và tổng số lá (Count Leaf Nodes) trong một Cây nhị phân sử dụng phương pháp đệ quy?

Bản chất cơ chế hoạt động

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 trees liên quan cùng chủ đề