Chương trình kiểm tra BST trong cây nhị phân và trả về gốc BST lớn nhất trong Python

Cho một cây nhị phân. Tìm cây con là Binary Search Tree (BST) lớn nhất (theo số nút). Trả về nút gốc của BST đó.

Ví dụ

Cây đầu vào: [1, 4, 6, 3, 5] (level-order)

    1
   / \
  4   6
 / \
3   5

Thuật toán

Giống bài trước nhưng chỉ trả về gốc BST thay vì tính tổng.

1. Biến c (kích thước max), m (gốc BST max)
2. Hàm recurse(node) post-order:
   • Đệ quy con trái, phải
   • Kiểm tra: left.val ≤ node.val ≤ right.val
   • Nếu BST: count = left_count + right_count + 1
   • Cập nhật max
3. Gọi recurse(root), trả về m

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 print_tree(root):
    if root is not None:
        print_tree(root.left)
        print(root.val, end=', ')
        print_tree(root.right)

def solve(root):
    c, m = 0, None
    
    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
    
    recurse(root)
    return m

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

Lưu ý

Code kiểm tra BST đơn giản: chỉ so sánh với con trực tiếp. Đúng khi duyệt post-order vì cây con đã được kiểm tra. Tuy nhiên, BST chuẩn yêu cầu: tất cả nút trong cây con trái < nút gốc < tất cả nút trong cây con phải. Code này chấp nhận cây con trái có nút lớn hơn gốc nếu nút đó không phải con trực tiếp (logic hơi lỏng). Để chặt chẽ hơn, cần trả về (min, max, is_bst, size) từ đệ quy.