Find the maximum path sum between any two tree nodes
A hiking app models a trail network as a binary tree of checkpoints. Each checkpoint has a score: positive for viewpoints and water, negative for steep climbs. A hiker can start at any checkpoint, walk along trail connections (up to a parent or down to a child), and finish at any checkpoint, never visiting one twice. The app wants the best score any such route can collect.
Implement maxPathSum(root). It returns the largest sum of node values over all paths in the tree.
maxPathSum(root) // => number, or null for an empty tree
{ value, left, right }. value is an integer (it can be negative or zero). left and right are nodes, null, or missing.null when root is null or undefined.// 4
// / \
// 9 6
// / \
// -2 8
maxPathSum(tree); // => 27 (9 → 4 → 6 → 8)
// -20
// / \
// 3 7
// / \
// 5 6
maxPathSum(tree); // => 18 (5 → 7 → 6, the root would only lower the sum)
// -5
// /
// -3
maxPathSum(tree); // => -3 (a single node is a valid path)
maxPathSum(null); // => null