Tìm cây con hoàn hảo lớn nhất trong cây nhị phân trong Python

Cho cây nhị phân, tìm kích thước cây con hoàn hảo (perfect binary tree) lớn nhất. Cây hoàn hảo: mọi nút nội bộ có 2 con, mọi lá ở cùng cấp.

Ví dụ: cây cho trước → kết quả 3 (cây con gốc 3 với 2 lá 5,6).

Giải thuật (Đệ quy post-order)

• Định nghĩa cấu trúc RetType chứa: isPerfect, height, rootTree.
• Đệ quy tính cho cây con trái và phải.
• Nếu cả hai cây con đều hoàn hảo và cùng chiều cao → cây hiện tại hoàn hảo, height = height_con + 1.
• Ngược lại: không hoàn hảo, height = max(height_trái, height_phải), rootTree trỏ đến cây con hoàn hảo lớn hơn.
• Kích thước cây hoàn hảo chiều cao h = 2^h - 1.

Ví dụ

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

def print_tree(root):
    if root:
        print_tree(root.left)
        print(root.data, end=', ')
        print_tree(root.right)

class RetType:
    def __init__(self):
        self.isPerfect = False
        self.height = 0
        self.rootTree = None

def get_perfect_subtree(root):
    r_type = RetType()
    if root is None:
        r_type.isPerfect = True
        r_type.height = 0
        r_type.rootTree = None
        return r_type
    left = get_perfect_subtree(root.left)
    right = get_perfect_subtree(root.right)
    if left.isPerfect and right.isPerfect and left.height == right.height:
        r_type.height = left.height + 1
        r_type.isPerfect = True
        r_type.rootTree = root
        return r_type
    r_type.isPerfect = False
    r_type.height = max(left.height, right.height)
    r_type.rootTree = left.rootTree if left.height > right.height else right.rootTree
    return r_type

root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.left.left = TreeNode(5)
root.left.right = TreeNode(6)
root.right.left = TreeNode(7)
res = get_perfect_subtree(root)
h = res.height
print("Size:", 2**h - 1)
print("Tree:", end=" ")
print_tree(res.rootTree)

Đầu vào

TreeNode(2) with left=3, right=4, left.left=5, left.right=6, right.left=7

Đầu ra

Size: 3 Tree: 5, 3, 6,