Compute maximum path sum in binary tree

Given the root of a binary tree where each node contains an integer value (which may be negative), return the maximum possible sum of values along any path in the tree. A path is defined as a sequence of nodes where each pair of adjacent nodes in the sequence is connected by a parent-child edge. The path: - Can start and end at any nodes in the tree. - Must contain at least one node. - Cannot jump between branches; it always follows child pointers up or down. For example, in the tree: -10 / \ 9 20 / \ 15 7 The maximum path sum is 42, using the path 15 -> 20 -> 7. Design an algorithm to compute this maximum path sum. Aim for O(n) time, where n is the number of nodes in the tree.