Maximum Sum of a BST Subtree

Gold

10000ms500MB

You are given the root of a binary tree whose nodes hold integer keys.

A subtree is one node of the tree together with all of its descendants. A subtree is a binary search tree when all three of these hold:

every key in the node's left subtree is smaller than the node's key;
every key in the node's right subtree is larger than the node's key;
the left subtree and the right subtree are binary search trees as well.

A single node is always a binary search tree.

Return the largest key sum over all subtrees that are binary search trees. The empty subtree counts as well, and its key sum is 0, so the answer is never negative.

Tree Encoding

Your function receives root as a TreeNode. The node type is provided for you, with val, left, and right fields.

The examples below write the tree as its level-order traversal, where null marks a missing child of a listed node and trailing nulls are omitted. That is only how the input is displayed; the decoding is done for you.

Constraints

The number of nodes in the tree is in the range $[1, 4 \times 10^4]$ .
$-4 \times 10^4 \leq$ Node.val $\leq 4 \times 10^4$

Examples

Example 1

Input

root = [

null,

]

root

Output

Explanation

The subtree rooted at the key 3 holds 3, 2, 5, 4 and 6, and it is a binary search tree, so its key sum 20 counts. The whole tree is not one, because the left child of the root holds 4 with a child holding 4 again.

Example 2

Input

root = [4, 3, null, 1, 2]

root

Output

Explanation

The subtree rooted at 3 is not a binary search tree, because its right child holds 2, which is smaller than 3. The best valid subtree is the single node holding 2.

Example 3

Input

root = [-4, -2, -5]

root

Output

Explanation

Every valid subtree here is a single node with a negative key, so the empty subtree and its key sum of 0 win.

Loading editor...

Run checks the sample cases; Submit runs every case.

Samples 3

Custom 0

passedwrong answertime limiterrorran, no expected valuenot run

sample

root =tree

Expected

Maximum Sum of a BST Subtree

Gold

10000ms500MB

You are given the root of a binary tree whose nodes hold integer keys.

A subtree is one node of the tree together with all of its descendants. A subtree is a binary search tree when all three of these hold:

every key in the node's left subtree is smaller than the node's key;
every key in the node's right subtree is larger than the node's key;
the left subtree and the right subtree are binary search trees as well.

A single node is always a binary search tree.

Return the largest key sum over all subtrees that are binary search trees. The empty subtree counts as well, and its key sum is 0, so the answer is never negative.

Tree Encoding

Your function receives root as a TreeNode. The node type is provided for you, with val, left, and right fields.

Constraints

The number of nodes in the tree is in the range $[1, 4 \times 10^4]$ .
$-4 \times 10^4 \leq$ Node.val $\leq 4 \times 10^4$

Examples

Example 1

Input

root = [

null,

]

root

Output

Explanation

Example 2

Input

root = [4, 3, null, 1, 2]

root

Output

Explanation

The subtree rooted at 3 is not a binary search tree, because its right child holds 2, which is smaller than 3. The best valid subtree is the single node holding 2.

Example 3

Input

root = [-4, -2, -5]

root

Output

Explanation

Every valid subtree here is a single node with a negative key, so the empty subtree and its key sum of 0 win.

Loading editor...

Run checks the sample cases; Submit runs every case.

Samples 3

Custom 0

passedwrong answertime limiterrorran, no expected valuenot run

sample

root =tree

Expected