Heaviest Path in a Tree

Hard

You are given the root of a binary tree whose nodes hold integers, possibly negative. A path is a sequence of nodes where every two neighbours are joined by an edge and no node appears twice. A path may start and end at any nodes, does not have to pass through the root, and may consist of a single node. The weight of a path is the sum of its node values. Return the largest weight of a non-empty path.

Example 1

root=tree_node([4, -7, 5, 3, 2, None, 6]) → 15

The best path is 4 → 5 → 6 with sum 15. Going into the left subtree does not pay off: -7 + 3 = -4.

Example 2

root=tree_node([-2, 8, 1, 3, -1]) → 11

The path does not have to go through the root: 3 → 8 gives 11, while adding the root -2 and node 1 only lowers the sum.

Example 3

root=tree_node([-5, -9]) → -5

Every value is negative, so the best path is the single node -5.

Constraints

1 ≤ number of nodes ≤ 3·10⁴
-1000 ≤ Node.val ≤ 1000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Dynamic Programming Binary Tree

Similar problems

Fewest Guards on a Tree Hard Heaviest Search Subtree Hard Biggest Search Subtree Medium A Party Without Direct Bosses Medium Zigzag Tree Descent Medium

Input

root=tree_node([4, -7, 5, 3, 2, None, 6])

Expected

Run checks the first 3 tests in your browser. Submit checks all 99 tests on the server, hidden ones included.