Maximum Sum of a Valid BST Subtree
Inside a large binary tree of signed metric values, find the subtree that is a valid binary search tree and has the greatest node-value sum. Report that maximum sum (0 if none is positive).
Problem
Given the root of a binary tree, return the maximum sum of all node values of any subtree that is also a valid Binary Search Tree (BST). A subtree must include all descendants of its root. If no BST subtree has a positive sum, return 0.
Input
The root of a binary tree, nodes carrying integer values (input given as a level-order array in examples).
Output
An integer: the maximum BST-subtree sum, or 0.
Constraints
- The number of nodes is in [1, 40000].
- -40000 <= Node.val <= 40000
Examples
Example 1
Input
root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
Output
20
The BST subtree rooted at the node with value 3 (containing 2,4,5 and 4,6) sums to 20.
Example 2
Input
root = [4,3,null,1,2]
Output
2
The single best positive-sum BST subtree sums to 2.