Mô phỏng thuật toán Đếm nút cây con

Subtree Node Count · Nhóm: Cây

Đếm số nút của cây con gốc tại mỗi nút bằng duyệt hậu thứ tự: xử lý xong cả hai con rồi mới cộng vào nút cha.

Ý tưởng

Duyệt DFS đi xuống tới lá, mỗi lá tính kích thước bằng 1.

Sau khi có kích thước con trái và con phải, đặt size[nút] = 1 + trái + phải.

Trả kích thước lên cho nút cha, cứ thế gộp dần lên tới gốc.

Vì sao đúng

Kích thước cây con là số liệu nền của nhiều thuật toán cây (tìm trọng tâm, cây phân tầng, truy vấn con), tính một lần bằng một lượt DFS.

Mã Python

def count(node):
    if node is None:
        return 0
    left = count(node.left)
    right = count(node.right)
    node.size = 1 + left + right
    return node.size

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.