在Python中查找给定二叉树中BST的最大总和值的程序

假设我们提供了一棵二叉树。 我们必须找出它的子树中是否存在二叉搜索树（BST），并找出最大BST的总和。 要找出总和，我们将添加该BST中每个节点的值。 我们将总和值作为输出返回。

因此，如果输入如下所示：

那么输出将为12。

给定的二叉树中的BST为 –

节点的总和= 12。

为了解决这个问题，我们将按照以下步骤操作:

• c:= 0
• m:= null
• value:= 0
• 定义recurse()函数。该函数将接收节点
  • 如果节点不为null，则
    • left_val:=递归（node的左子节点）
    • right_val:=递归（node的右子节点）
    • count:=负无穷
    • 如果（节点的左节点为null或节点的左节点的值≤节点的值）和（右节点节点为null或节点的值≤节点的右节点的值） 则
    • count:=left_val+right_val+1
    • 如果count>c，则
    • c:=count
    • m:=node
    • 返回count
  • 返回0
• 定义calculate_sum()函数。该函数将接收根
  • 如果根不为空，则
    • calculate_sum（root的左子树）
    • value:=value+root的值
    • calculate_sum（root的右子树）
• recurse(root)
• calculate_sum（m）
• 返回value

例子

让我们看看以下实现以更好地理解−

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, 0def recurse(node):
        if node:
            nonlocal c, m
            left_val = recurse(node.left)
            right_val = recurse(node.right)
            count = -float("inf")
            if (node.left == None or node.left.val <= node.val) and (node.right == 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))

输入

tree = make_tree([1, 4, 6, 3, 5])
print(solve(tree))

输出

12