A path in a binary tree is any sequence of nodes where consecutive nodes are connected by an edge and no node appears twice. The path does not have to pass through the root and does not need to end at a leaf; it must contain at least one node. Return the largest possible sum of node values along such a path.
Examples
-10
/ \
9 20
/ \
15 7
Input: root = build_tree([-10, 9, 20, None, None, 15, 7])
Output: 42
Explanation: 15 -> 20 -> 7.
Input: root = build_tree([1, 2, 3])
Output: 6
Input: root = build_tree([-3])
Output: -3
Constraints
1 <= number of nodes <= 1000-1000 <= node.val <= 1000
Goals
- Distinguish the value a subtree returns upward from the value it contributes to the global answer
- Use max(x, 0) to ignore harmful branches