Compute maximum path sum in a binary tree

You are given the root of a binary tree where each node contains an integer value (which may be positive, zero, or negative). A **path** in the tree is defined as any sequence of nodes such that: - Each pair of consecutive nodes in the sequence is connected by an edge in the tree. - A path may start and end at any nodes in the tree. - A path must contain at least one node. - The path cannot reuse the same node more than once (i.e., it is a simple path; it does not branch or form cycles). The **path sum** is the sum of the node values along that path. ### Task Implement a function that returns the **maximum path sum** over all possible paths in the tree. ### Function Signature You can assume a typical binary tree node definition, for example in a C++/Java-like style: ```text class TreeNode { int val; TreeNode left; TreeNode right; } ``` Write a function: ```text int maxPathSum(TreeNode root) ``` which returns the maximum path sum. ### Constraints - The number of nodes in the tree is in the range [1, 3 * 10^4]. - Each node value is in the range [-10^3, 10^3]. - The tree is not necessarily balanced. ### Examples **Example 1** Input tree (level-order representation): `[1, 2, 3]` This corresponds to the structure: ```text 1 / \ 2 3 ``` All possible simple paths and their sums: - 2 → 1 → 3 has sum 2 + 1 + 3 = 6 - 2 → 1 has sum 3 - 1 → 3 has sum 4 - Single-node paths: 2, 1, 3 Output: `6` **Example 2** Input tree (level-order): `[-10, 9, 20, null, null, 15, 7]` Structure: ```text -10 / \ 9 20 / \ 15 7 ``` The maximum path is 15 → 20 → 7 with sum 15 + 20 + 7 = 42. Output: `42` **Example 3** Input tree (single node): `[-3]` Only one possible path: the single node itself. Output: `-3` ### Notes - The maximum path is allowed to start and end at any two nodes in the tree. - The path is not required to pass through the root.