Mô phỏng thuật toán DP trên cây · tổng cây con

Tree DP · Subtree Sum · Nhóm: Quy hoạch động

Quy hoạch động trên cây: tổng giá trị của mỗi cây con bằng giá trị nút cộng tổng hai cây con, tính theo duyệt hậu thứ tự.

Ý tưởng

DFS đi xuống, lá trả về chính giá trị của nó.

Nút trong lấy tổng con trái và con phải đã tính xong.

Đặt sum[nút] = val[nút] + tổng-trái + tổng-phải, trả lên cha.

Vì sao đúng

Đây là mẫu quy hoạch động trên cây điển hình: mỗi nút gộp kết quả của các con, tính toàn cây chỉ trong một lượt duyệt.

Mã Python

def subtree_sum(node):
    if node is None:
        return 0
    left = subtree_sum(node.left)
    right = subtree_sum(node.right)
    node.sum = node.val + left + right
    return node.sum

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