Mô phỏng thuật toán DP trên cây · đường kính

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

Quy hoạch động trên cây tìm đường kính, tức số cạnh của đường đi dài nhất: tại mỗi nút, đường đi dài nhất đi qua nó bằng chiều cao con trái cộng chiều cao con phải.

Ý tưởng

DFS tính chiều cao mỗi nút: 1 cộng chiều cao con cao hơn.

Tại mỗi nút, xét đường đi qua nó = chiều cao trái + chiều cao phải.

Giữ giá trị lớn nhất của các đường đi-qua-nút, đó là đường kính.

Vì sao đúng

Đường kính đo phạm vi trải rộng của cây, tính gọn trong một lượt DFS mà không cần chạy nhiều lần từ mỗi nút.

Mã Python

best = 0
def height(node):
    if node is None:
        return 0
    l = height(node.left)
    r = height(node.right)
    best = max(best, l + r)   # path through node
    return 1 + max(l, r)

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