Chương trình tìm tổng lớn nhất của BST trong cây nhị phân cho trước trong Python

Cho một cây nhị phân. Tìm cây con là Binary Search Tree (BST) có tổng giá trị nút lớn nhất. Trả về tổng đó.

Ví dụ

Cây đầu vào:

    1
   / \
  4   6
 / \
3   5

Thuật toán (Post-order DFS)

Duyệt hậu tự (post-order) để kiểm tra từng cây con có phải BST không. Với mỗi nút, trả về số nút của BST lớn nhất gốc tại nút đó.

1. Biến toàn cục: c (kích thước BST lớn nhất), m (gốc BST lớn nhất), value (tổng)
2. Hàm recurse(node):
   • Đệ quy trái, phải
   • Kiểm tra tính chất BST: nút trái ≤ nút hiện tại ≤ nút phải
   • Nếu thỏa mãn: count = left_count + right_count + 1
   • Cập nhật BST lớn nhất nếu count > c
   • Trả về count (hoặc -inf nếu không phải BST)
3. Hàm calculate_sum(root): duyệt in-order tính tổng nút của BST tìm được

Mã nguồn

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

def insert(temp, data):
    que = [temp]
    while que:
        temp = que.pop(0)
        if not temp.left:
            temp.left = TreeNode(data) if data is not None else TreeNode(0)
            break
        else:
            que.append(temp.left)
        if not temp.right:
            temp.right = TreeNode(data) if data is not None else TreeNode(0)
            break
        else:
            que.append(temp.right)

def make_tree(elements):
    tree = TreeNode(elements[0])
    for element in elements[1:]:
        insert(tree, element)
    return tree

def solve(root):
    c, m, value = 0, None, 0
    
    def recurse(node):
        nonlocal c, m
        if node:
            left_val = recurse(node.left)
            right_val = recurse(node.right)
            count = -float("inf")
            if (node.left is None or node.left.val <= node.val) and \
               (node.right is None or node.val <= node.right.val):
                count = left_val + right_val + 1
            if count > c:
                c = count
                m = node
            return count
        return 0
    
    def calculate_sum(root):
        nonlocal value
        if root is not None:
            calculate_sum(root.left)
            value += root.val
            calculate_sum(root.right)
    
    recurse(root)
    calculate_sum(m)
    return value

tree = make_tree([1, 4, 6, 3, 5])
print(solve(tree))  # Output: 12

Phân tích

• Độ phức tạp: O(n) thời gian, O(h) không gian (h = chiều cao cây)
• Logic kiểm tra BST: chỉ kiểm tra nút con trực tiếp, giả định cây con đã là BST (đảm bảo bởi post-order)
• Cây trong ví dụ được xây dựng bằng level-order insertion từ mảng [1,4,6,3,5]