942. Maximum Sum BST in Binary Tree

Given the root of a binary tree, return the maximum sum of node values of any subtree that is itself a valid binary search tree. If every valid-BST subtree has a negative sum, the answer may be 0 (the empty subtree). The tree is given as a level-order array.

Input: A level-order array of the tree.

Output: Integer — the maximum BST subtree sum.

Examples

Input: [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
Output: 20
Explanation: The BST subtree (3,2,5,4,6) sums to 20.

Input: [4,3,null,1,2]
Output: 2
Explanation: Best BST subtree sum.

Input: [-4,-2,-5]
Output: 0
Explanation: All negative; empty subtree gives 0.

Constraints

• 1<=nodes<=4*10^4
• -4*10^4<=value<=4*10^4

Asked by