Facebook PixelBinary Tree Maximum Path Sum — Coding Practice
Binary Tree Maximum Path SumHard

Binary Tree Maximum Path Sum

Hard 16.2k40% acceptance
TreeDepth-First SearchDynamic ProgrammingBinary 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 where each consecutive pair is connected by an edge; a node appears at most once and the path does not have to pass through the root. The path sum is the total of the node values along it. Every path has at least one node.

The tree is given in level-order (TreeNode with { val, left, right }, null for a missing child).

Example 1
Input: root = [1,2,3]
Output: 6
The path 2 → 1 → 3 sums to 6.
Example 2
Input: root = [-10,9,20,null,null,15,7]
Output: 42
The path 15 → 20 → 7 sums to 42; including the negative root would only reduce it.
Example 3
Input: root = [-3]
Output: -3
With a single node the best (and only) path is that node itself.
Constraints
  • The number of nodes is in the range [1, 3·10⁴].
  • -1000 ≤ Node.val ≤ 1000
Asked atAmazonMicrosoftMetaGoogle
JavaScript
Loading editor…
Case 1
[1,2,3]
expected: 6
Case 2
[-10,9,20,null,null,15,7]
expected: 42
Case 3
[-3]
expected: -3
Case 4
[2,-1]
expected: 2
Case 5
[5]
expected: 5
Case 6
[-2,-1]
expected: -1
Case 7
[1,-2,-3,1,3,-2,null,-1]
expected: 3