Subtree with Maximum Value

Given a binary tree root, return the maximum sum of a subtree. A subtree is defined to be some node in root including all of its descendants. A subtree sum is the sum of all the node values in the subtree. A subtree can be null in which case its sum is 0.

Constraints

• 1 ≤ n ≤ 100,000 where n is the number of nodes in root

https://binarysearch.com/problems/Subtree-with-Maximum-Value

Examples

Example 1

Input

• root =

Output

• answer = 5

Solution