Maximum Sum BST in Binary Tree:

You get the root of a binary tree. Return the largest sum of values in a subtree that is a binary search tree (BST).

A subtree is a node together with everything below it. It is a BST when this holds at each of its nodes:

• every value in the node's left subtree is smaller than the node's value,
• every value in its right subtree is larger.

An empty tree also counts as a BST, with a sum of 0. So the answer is never below 0.

The trees below are listed level by level, top to bottom and left to right. A missing child is written as nil.

Example 1:

Input: root = [6,9,3,4,11,nil,2,1,5]
Output: 30
Explanation: The blue subtree starts at 9.
It is a BST: 1 < 4 < 5 < 9 < 11.
Its sum is 9 + 4 + 11 + 1 + 5 = 30.
The whole tree is not a BST: 9 is left of 6 but larger.
The subtree from 3 down is not a BST: 2 is right of 3 but smaller.

Example 2:

Input: root = [-5,-8,4,-9,7]
Output: 7
Explanation: The subtree from -8 down is a BST, but its sum is -10.
The whole tree is not a BST: 7 is left of -5 but larger.
The best BST is the single blue node 7.

Example 3:

Input: root = [-3,-6,-1]
Output: 0
Explanation: The whole tree is a BST, but every value is negative.
So any BST with nodes in it has a sum below 0.
The empty tree, with sum 0, is the best.

Constraints:

• 1 to 25,000 nodes.
• Each value is from -10,000 to 10,000.
• The tree can be up to 10,000 levels deep.