Find the Heaviest Path Anywhere in the Tree
Implement bestBendSum
You are given the root of a binary tree of integers (which may be negative). A path is a sequence of connected nodes that goes down one side of some node and, optionally, down the other side as well; it can start and end at any nodes and cannot use a node twice. The weight of a path is the sum of its node values. Return the largest weight over all non-empty paths — or 0 if the tree is empty.
The best path that bends at a node uses the better branch on each side of it, ignoring a branch that would lower the sum. Computing those branches bottom-up gives an O(n) solution.
Example 1:
Input: root = [-4,8,6,-2,5,null,-3,7]
Output: 18
Example 2:
Input: root = [-7]
Output: -7
Example 3:
Input: root = [-5,-2,-9]
Output: -2
+ 13 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ number of nodes ≤ 100 - ●
−100 ≤ node.val ≤ 100 - ●
The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child - ●
A path is a chain of at least one node in which each consecutive pair is joined by a parent-child connection; it may start and end at ANY nodes and may bend once at its highest node (going down one side, then down the other), but it may not visit a node twice. Return the largest sum of node values over all paths (0 for an empty tree). The answer may be negative when every value is negative
root =