Find the maximum sum of any path in a binary tree, where the path can start and end at any nodes but must follow parent-child links.
Given the root of a binary tree, find the maximum possible sum of values along any non-empty path in the tree.
A path is a sequence of nodes connected by edges where each adjacent pair is directly connected by a parent-child link. The path does not need to pass through the root, and it may start and end at any two nodes. Each node can appear at most once in the path.
The path must contain at least one node.
Your task is to return the largest path sum that can be formed in the tree.
Example 1
Input
root = [1,2,3]
Output
6
Explanation
The best path is 2 -> 1 -> 3, with sum 6.
Example 2
Input
root = [-10,9,20,null,null,15,7]
Output
42
Explanation
The best path is 15 -> 20 -> 7, with sum 42.
Example 3
Input
root = [-3]
Output
-3
Explanation
With a single node, the only path is the node itself.
Premium problem context
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.