โปรแกรมหาผลรวม BST สูงสุดใน Binary Tree ใน Python

กำหนด Binary Tree ต้องการหาว่ามี Binary Search Tree (BST) ในซับทรีหรือไม่ และหาผลรวมของ BST ที่ใหญ่ที่สุด ผลรวมคำนวณจากค่าของทุกโหนดใน BST นั้น

ตัวอย่าง

ผลลัพธ์: 12

BST ที่พบ:

ผลรวมโหนด = 3 + 4 + 5 = 12

วิธีแก้ปัญหา

1. ใช้ DFS (Post-order traversal) ตรวจสอบแต่ละซับทรีว่าเป็น BST หรือไม่
2. ติดตามขนาด BST ที่ใหญ่ที่สุด (c) และรูทของมัน (m)
3. คำนวณผลรวมโหนดของ BST ที่ใหญ่ที่สุด

เงื่อนไข BST

• โหนดซ้าย ≤ โหนดปัจจุบัน ≤ โหนดขวา
• ซับทรีซ้ายและขวาต้องเป็น BST ด้วย

ตัวอย่างโค้ด

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

def insert(temp, data):
    que = []
    que.append(temp)
    while len(que):
        temp = que[0]
        que.pop(0)
        if not temp.left:
            if data is not None:
                temp.left = TreeNode(data)
            else:
                temp.left = TreeNode(0)
            break
        else:
            que.append(temp.left)
        if not temp.right:
            if data is not None:
                temp.right = TreeNode(data)
            else:
                temp.right = 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))

อินพุต / เอาต์พุต

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

หมายเหตุ: โค้ดนี้ใช้การสร้างต้นไม้แบบ level-order insertion โครงสร้างต้นไม้ขึ้นอยู่กับลำดับการ insert