Skip to content
BASA DSA

Binary Tree Maximum Path Sum

HardTrees

Return the maximum sum of a nonempty simple path in a binary tree. A path can begin and end anywhere and may not repeat a node.

Example 1

Argument 1 tree: level-order input; omitted children are null.Argument 1 tree: level-order input; omitted children are null. Vertices: node 0: -5, node 1: 4, node 2: 8, node 3: 3, node 4: 9. Edges: node 0 (-5) — node 1 (4) left child; node 0 (-5) — node 2 (8) right child; node 2 (8) — node 3 (3) left child; node 2 (8) — node 4 (9) right child.-54839
Argument 1 tree: level-order input; omitted children are null.

Input
root = [-5,4,8,null,null,3,9]
Output
20

Explanation

The best path 3->8->9 totals 20; extending through -5 lowers its sum.

Example 2

Argument 1 tree: level-order input; omitted children are null.Argument 1 tree: level-order input; omitted children are null. Vertices: node 0: -8, node 1: -3, node 2: -6. Edges: node 0 (-8) — node 1 (-3) left child; node 0 (-8) — node 2 (-6) right child.-8-3-6
Argument 1 tree: level-order input; omitted children are null.

Input
root = [-8,-3,-6]
Output
-3

Explanation

The path must be nonempty, so choose least-negative node -3.

Example 3

Argument 1 tree: level-order input; omitted children are null.Argument 1 tree: level-order input; omitted children are null. Vertices: node 0: 2. Edges: none.2
Argument 1 tree: level-order input; omitted children are null.

Input
root = [2]
Output
2

Explanation

The only path contains value 2.

Constraints

  • 1 <= number of nodes <= 10000
  • Values are -1000..1000

Function contractmaxPathSumArguments: tree
Loading draft…
SolutionRuns on your device