noodleProblems/
Binary Tree Maximum Path Sum
#137

Binary Tree Maximum Path Sum

AlgorithmhardDynamic ProgrammingTreeDepth First SearchBinary Tree

Given the root of a binary tree, return the maximum **path sum** of any non-empty path.

A path is any sequence of nodes connected by parent–child edges; it need **not** pass through the root, and each node appears at most once. A path can turn at one node (going down its left side and up into its right side) but cannot branch at two nodes. The sum is the total of the values on the path.

The tree is given as a level-order array where null marks a missing child: [-10, 9, 20, null, null, 15, 7].

Example cases

  • turn at root
    in root = [1,2,3]213
    out 6
    2 → 1 → 3 sums to 6.
  • skip the root
    in root = [-10,9,20,null,null,15,7]9-1015207
    out 42
    15 → 20 → 7 sums to 42; the negative root is excluded.
  • single node
    in root = [-3]-3
    out -3
    A path must be non-empty, so the best is the lone node.

Constraints

  • The number of nodes in the tree is in the range [1, 3 * 10^4].
  • -1000 <= Node.val <= 1000
Saved
root =
[1,2,3]