Binary Tree Maximum Path Sum

Trees: DFS & BFS, problem 8 of 8

Binary Tree Maximum Path Sum

Hard

LC #124

dfsglobal best

Not attempted yet

A path in a binary tree is a sequence of nodes where each adjacent pair is connected by an edge, and no node appears twice. It does not need to pass through the root and may go up then down (bending at one node). It must contain at least one node.

Given the root, return the largest sum of values along any path.

Example 1

Input: root = [1, 2, 3]
Output: 6

Path 2 → 1 → 3.

Example 2

Input: root = [-10, 9, 20, None, None, 15, 7]
Output: 42

Path 15 → 20 → 7; the root only makes it worse.

Example 3

Input: root = [-3]
Output: -3

Constraints

  • 1 ≤ number of nodes ≤ 3 · 10^4
  • -1000 ≤ Node.val ≤ 1000

Python

Loading draft…

Test results

8 tests available

No results yet

Run tests your code against the examples; Submit runs the hidden tests too.

3 examples, 5 hidden

Run examples, then submit all tests.