Khóa học Python từ Cơ bản đến Nâng cao

Bài 14.4 - Bài tập Python: tìm LCA đơn giản

Trong cây, LCA (Lowest Common Ancestor) là tổ tiên chung gần nhất của hai node. Đây là một bài toán cơ bản nhưng cực kỳ phổ biến trong các kỳ thi và phỏng vấn lập trình.

Hôm nay chúng ta sẽ cùng nhau giải bài toán tìm LCA một cách đơn giản bằng Python nhé!

1. Mô hình cây đơn giản

Chúng ta dùng cấu trúc cây cơ bản như sau:

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

Giải thích:

• Mỗi Node có giá trị value, con trái left và con phải right.

2. Hàm tìm tổ tiên chung (LCA)

def find_lca(root, n1, n2):
    if root is None:
        return None
    if root.value == n1 or root.value == n2:
        return root

    left_lca = find_lca(root.left, n1, n2)
    right_lca = find_lca(root.right, n1, n2)

    if left_lca and right_lca:
        return root
    return left_lca if left_lca else right_lca

Giải thích:

• Nếu root là 1 trong 2 node cần tìm, trả về root.
• Tìm đệ quy trong cây con trái và cây con phải.
• Nếu cả hai bên đều có kết quả, root chính là LCA.

3. Ví dụ 1: Cây nhị phân nhỏ

# Tạo cây
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)

# Tìm LCA của 4 và 5
lca_node = find_lca(root, 4, 5)
print("LCA của 4 và 5 là:", lca_node.value)

✅ Kết quả:

LCA của 4 và 5 là: 2

Giải thích:

• 4 và 5 đều là con của 2 → node 2 là tổ tiên chung gần nhất.

4. Ví dụ 2: LCA ở gốc

lca_node = find_lca(root, 4, 6)
print("LCA của 4 và 6 là:", lca_node.value)

✅ Kết quả:

LCA của 4 và 6 là: 1

Giải thích:

• 4 ở nhánh trái, 6 ở nhánh phải → node gốc (1) là tổ tiên chung gần nhất.

5. Ví dụ 3: Một node là tổ tiên của node còn lại

lca_node = find_lca(root, 2, 4)
print("LCA của 2 và 4 là:", lca_node.value)

✅ Kết quả:

LCA của 2 và 4 là: 2

Giải thích:

• Node 2 là tổ tiên trực tiếp của 4.

Kết luận

Tìm LCA là một bài toán cực kỳ hữu ích, ứng dụng nhiều trong xử lý cây, phân tích dữ liệu phân cấp, cây phân loại, v.v. Với cách tiếp cận đệ quy đơn giản như trên, bạn đã có thể xử lý tốt các cây nhị phân cơ bản.

💡 Bạn có thể mở rộng bài toán cho cây không phải nhị phân hoặc lưu parent pointer để tối ưu hơn.

#HappyCoding cùng FullhouseDev! 🚀