Optimal Tree Route Sum

A route in a binary tree is defined as a continuous sequence of nodes where consecutive nodes in the sequence share a direct parent-child edge connection. Each node in the tree can participate in the route at most once — meaning the route cannot revisit or loop through any node. Importantly, the route does not have to traverse through the root node; it can begin and end at any nodes within the tree.

The route sum represents the cumulative total of all node values along the chosen route.

Given the root of a binary tree containing integer values (which may be positive, negative, or zero), your task is to determine and return the maximum route sum achievable by any valid non-empty route in the tree.

Key Observations:

• A route can span from any node to any other node in the tree, as long as the path between them consists of valid parent-child edges.
• The route can consist of a single node (useful when all paths yield negative sums).
• Since node values can be negative, strategic selection of which nodes to include is crucial for maximizing the sum.
• The optimal route might be entirely contained within a subtree, not necessarily passing through higher-level nodes.