A path is any sequence of nodes connected by edges where each node appears at most once.
Given the root of a binary tree, return the maximum path sum of any non-empty path.
Reason about the value returned from each subtree and the state passed down from ancestors. Empty children and single-node trees should be handled naturally.
Examples
Input: root = [1,2,3] Output: 6
Input: root = [-10,9,20,null,null,15,7] Output: 42
Constraints
- The number of nodes in the tree is in the range [1, 30,000].
- -1,000 <= Node.val <= 1,000