Làm thế nào để đếm tổng số nút (Count Nodes) trong một Cây nhị phân hoàn chỉnh (Complete Binary Tree) với hiệu năng tối ưu?

Question

Accepted Answer

Bản chất cơ chế hoạt động Đối với một Cây nhị phân thông thường, việc đếm số nút đòi hỏi phải duyệt qua toàn bộ N nút với độ phức tạp thời gian O(N). Tuy nhiên, nếu đề bài cung cấp cấu trúc là Cây nhị phân hoàn chỉnh (Complete Binary Tree), chúng ta có thể tận dụng tính chất cân bằng để tối ưu hóa thời gian xuống dưới O(N), cụ thể là O(log N * log N). Ví dụ mã nguồn minh họa def countNodes(root: TreeNode) -> int: if not root: return 0 left_depth = getDepth(root.left) right_depth = getDepth(root.right) if left_depth == right_depth: # Cây con bên trái là cây hoàn chỉnh đầy đủ return (1 << left_depth) + countNodes(root.right) else: # Cây con bên phải là cây hoàn chỉnh có chiều cao nhỏ hơn 1 return (1 << right_depth) + countNodes(root.left) def getDepth(node: TreeNode) -> int: depth = 0 while node: depth += 1 node = node.left return depth Lưu ý kinh nghiệm thực chiến Tư duy tối ưu: Phỏng vấn viên ở cấp độ Junior thường đánh giá cao ứng viên biết phân tích đặc thù cấu trúc dữ liệu thay vì chỉ áp dụng thuật toán duyệt vét cạn (Brute Force). Tránh lỗi tràn số: Khi sử dụng phép dịch bit (1 << depth), hãy đảm bảo ngôn ngữ lập trình hỗ trợ kiểu số nguyên lớn nếu chiều cao của cây vượt quá giới hạn của kiểu dữ liệu 32-bit.

Làm thế nào để đếm tổng số nút (Count Nodes) trong một Cây nhị phân hoàn chỉnh (Complete Binary Tree) với hiệu năng tối ưu?

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