Chương trình tìm tổ tiên chung gần nhất của hai nút trong cây nhị phân bằng Python

Cho cây nhị phân và hai giá trị a, b. Tìm giá trị của nút thấp nhất (lowest common ancestor) có cả a và b là hậu duệ. Nút coi là hậu duệ của chính nó.

Ví dụ: a = 6, b = 2 → 4.

Quy trình giải quyết (Đệ quy)

1. Nếu gốc null, trả về -1.
2. Nếu giá trị gốc bằng a hoặc b, trả về giá trị gốc.
3. Đệ quy tìm ở con trái (left) và con phải (right).
4. Nếu cả left và right khác -1, trả về giá trị gốc (tổ tiên chung).
5. Ngược lại trả về left nếu khác -1, nếu không trả về right.

Ví dụ mã nguồn

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def solve(self, root, a, b):
        if not root:
            return -1
        if root.val in (a, b):
            return root.val
        left = self.solve(root.left, a, b)
        right = self.solve(root.right, a, b)
        if -1 not in (left, right):
            return root.val
        return left if left != -1 else right

ob = Solution()
root = TreeNode(3)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)
print(ob.solve(root, 6, 2))  # Output: 4

Đầu vào

root = TreeNode(3) root.left = TreeNode(10) root.right = TreeNode(4) root.right.left = TreeNode(8) root.right.right = TreeNode(2) root.right.left.left = TreeNode(6) 6, 2

Đầu ra

4