Given the root of a binary tree, return the maximum path sum of any non-empty path in the tree.
Description
Binary Tree Maximum Path Sum
A path is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A path must contain at least one node and does not need to go through the root.
The path sum of a path is the sum of the node values along that path.
Return the maximum path sum of any path in the binary tree.
Output Format
Return the maximum path sum of any non-empty path in the binary tree.
Constraints
The exact constraints are not provided in the source metadata. In the LeetCode version, the tree is finite and node values may be negative.
Example 1
Input
root = [1,2,3]
Output
6
Explanation
The optimal path is 2 -> 1 -> 3, with sum 6.
Example 2
Input
root = [-10,9,20,null,null,15,7]
Output
42
Explanation
The optimal path is 15 -> 20 -> 7, with sum 42.
Premium problem context
Unlock deeper context for this problem
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.