Tìm cây con lớn nhất có cây con trái và phải giống hệt nhau trong Python

Cho cây nhị phân, tìm cây con lớn nhất có cây con trái và phải identical (giống hệt nhau về cấu trúc và giá trị). Yêu cầu độ phức tạp O(n).

Ví dụ: cây gốc root=55, cây con root=70 có hai nhánh trái/phải đều là 75→(65,80) → Kích thước 7.

Thuật toán mã hóa cây (Tree Encoding)

1. Hàm solve(root, encode, maxSize, maxNode) trả về kích thước cây con tại root.
2. Đệ quy tính size trái ls và phải rs, lấy encoding chuỗi của cây con trái/phải.
3. Nếu encoding trái == encoding phải: cập nhật maxSize và maxNode nếu size lớn hơn.
4. Encoding của nút hiện tại: "|" + left_encode + "|" + str(data) + "|" + right_encode + "|".
5. Trả về size = ls + rs + 1.

Ví dụ code

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

def solve(root, encode, maxSize, maxNode):
    if root is None:
        return 0
    left_list = [""]
    right_list = [""]
    ls = solve(root.left, left_list, maxSize, maxNode)
    rs = solve(root.right, right_list, maxSize, maxNode)
    size = ls + rs + 1
    if left_list[0] == right_list[0]:
        if size > maxSize[0]:
            maxSize[0] = size
            maxNode[0] = root
    encode[0] = encode[0] + "|" + left_list[0] + "|"
    encode[0] = encode[0] + "|" + str(root.data) + "|"
    encode[0] = encode[0] + "|" + right_list[0] + "|"
    return size

def largestSubtree(node, maxNode):
    maximum = [0]
    encode = [""]
    solve(node, encode, maximum, maxNode)
    return maximum

# Xây dựng cây ví dụ
root = TreeNode(55)
root.left = TreeNode(15)
root.right = TreeNode(70)
root.left.left = TreeNode(10)
root.left.right = TreeNode(25)
root.right.left = TreeNode(75)
root.right.left.left = TreeNode(65)
root.right.left.right = TreeNode(80)
root.right.right = TreeNode(75)
root.right.right.left = TreeNode(65)
root.right.right.right = TreeNode(80)

maxNode = [None]
maximum = largestSubtree(root, maxNode)
print("Root of largest sub-tree", maxNode[0].data)
print("and its size is", maximum)

Input

Cây nhị phân như mô tả

Output

Root of largest sub-tree 70
and its size is [7]