Maximum Sum BST in Binary Tree

Hard

Given the root of a binary tree, return the maximum sum of all keys of any sub-tree which is also a Binary Search Tree (BST). A valid BST requires every node in the left subtree to be strictly less than the node, and every node in the right subtree to be strictly greater. If no sub-tree is a BST with positive sum, return 0.

Example 1

Input:  root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
Output: 20

Example 2

Input:  root = [4,3,null,1,2]
Output: 2

Example 3

Input:  root = [-4,-2,-5]
Output: 0

Constraints

• 1 <= number of nodes <= 4*10^4
• -4*10^4 <= Node.val <= 4*10^4.