You are given root, the root of a non-empty binary tree whose values may be negative.
A path is a sequence of nodes, each linked to the next by a parent–child edge, that never visits a node twice. It has at least one node and need not pass through the root. Its sum is the total of its nodes' values.
Return the largest sum of any path.
Trees are written in level order, row by row from the top, with null where a node is missing:
[4, 2, 7, null, 3] is 4 at the root, 2 and 7 below it, and 3 as the right child of 2.
Example 1
- Input
- root = [4, -7, 6, 3, 2, 5, -1]
- Output
- 15
Example 2
- Input
- root = [-5, -2, -9]
- Output
- -2
Constraints
- The tree holds 1 to 1000 nodes.
- Every value is between −1000 and 1000.
Show the pattern
Trees
The best path turns at some highest node and takes the best downward chain on each side, but only when that chain helps. A post-order pass returns each node's best downward chain and scores every turn on the way.
See trees in a visualiserShow the approach
For each node, let gain(node) be the best sum of a path that starts at the node and goes
straight down. It is the node's value plus the better of its children's gains, where a child's
gain only counts if it is positive (an empty child counts as 0).
Every path has a highest node, where it may turn. The best path turning at a node is its value
plus the positive part of each child's gain. A post-order recursion computes gain for every
node and updates the best turning sum as it goes. Start the best at the root's value rather
than 0, since a path must hold at least one node and every value may be negative.
Time: O(n) · Space: O(h) for the recursion, h the tree's height