Mô phỏng thuật toán Tổ tiên chung gần nhất

Lowest Common Ancestor · Nhóm: Cây

Tổ tiên chung gần nhất (Lowest Common Ancestor), nhóm Cây.

Mã Python

def lca(a, b):
    # climb from a to root, mark ancestors
    ancestors = set()
    node = a
    while node is not None:
        ancestors.add(node)
        node = node.parent
    # climb from b: first marked ancestor is LCA
    node = b
    while node is not None:
        if node in ancestors:
            return node
        node = node.parent
    return None

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