Best Path Sum in a Tree

A path in a binary tree is a sequence of nodes where each pair of neighbours in the sequence is joined by an edge, and no node appears twice. A path does not have to pass through the root, and it can be a single node.

You are given the root of a non-empty binary tree. Return the largest sum of the values along any path.

Trees in the examples are written level by level, left to right, with null where a child is missing: [1,null,2] is a root 1 with only a right child, 2. [] is an empty tree, with no root at all.

Constraints

  • 1 ≤ number of nodes ≤ 10,000
  • -1,000 ≤ node value ≤ 1,000
  • The tree is at most 1,000 levels deep.

Example 1

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

The path 2 → 1 → 3 adds up to 6.

Example 2

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

15 → 20 → 7 adds up to 42. Going through the root would add -10.

Example 3

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

A path has at least one node, even when every value is negative.

Hints

    Was this a good challenge?

    Solved by
    0
    Submissions
    0
    Accepted
    –