Binary Tree Maximum Path Sum

Binary TreeDepth-First SearchDynamic ProgrammingTree

Given the root of a binary tree, find the maximum path sum. The path must be a contiguous sequence of nodes in which the sum of the values is maximized. This path can include any number of nodes and may start and end at any node in the tree.

Example 1

Input

Output

Explanation. The optimal path is `2 -> 1 -> 3` which has a path sum of 6.

Example 2

Input

[
  [
    -10,
    9,
    20,
    null,
    null,
    15,
    7
  ]
]

Output

Explanation. The optimal path is `15 -> 20 -> 7`. No path through the root (-10) can achieve a sum greater than 42.

Example 3

Input

[
  [
    1
  ]
]

Output

Explanation. There's only one node, and thus the maximum path sum is the value of that node itself.

Example 4

Input

[
  [
    -5,
    -4,
    -2,
    -1
  ]
]

Output

-1

Explanation. All nodes are negative. The least negative number is the max sum which is the node with value -1.

Follow-up: Can you improve the algorithm to run in linear time?

Constraints:

The number of nodes in the tree is in the range [1, 3 * 10^4]. Each node's value is between [-1000, 1000].

Views: 2