Viết hàm Java đếm số lượng nút trong cây
Viết hàm Java đếm số lượng nút trong cây
Cách chuẩn là duyệt toàn bộ cây: mỗi nút đếm đúng một lần. Nếu gốc null thì trả 0; không thì kết quả bằng 1 cộng số nút cây con trái và phải. Thời gian O(n), bộ nhớ O(h) do stack đệ quy (h là chiều cao; cây lệch có thể O(n)).
int count(TreeNode root) {
return root == null ? 0 : 1 + count(root.left) + count(root.right);
}
Nếu không muốn đệ quy, dùng stack hoặc BFS: mỗi lần lấy một nút ra thì tăng biến đếm, rồi đẩy các con khác null vào hàng đợi. Độ phức tạp thời gian vẫn O(n).
Hai tối ưu hay được hỏi thêm. Nếu mỗi nút BST (hoặc cây bất kỳ) lưu sẵn size — số nút của cây con gốc tại đó — thì đếm cả cây chỉ là đọc root.size, O(1), miễn là bạn cập nhật size khi chèn/xóa. Với cây complete (mọi tầng đầy trừ tầng cuối, các nút sát về bên trái), có thể đếm trong O(log² n): so sánh chiều cao cây con trái và phải. Nếu bằng nhau, cây con trái là cây đầy (perfect) nên có đúng 2^h - 1 nút, chỉ cần đệ quy vào bên phải; nếu lệch thì bên phải là perfect, đệ quy vào bên trái. Mỗi lần đo chiều cao tốn O(log n), số lần đo cũng O(log n).
Đăng nhập để tham gia thảo luận cùng mọi người.
Chưa có bình luận nào
Hãy là người đầu tiên chia sẻ suy nghĩ của bạn.