DSAhardTrees~35m

The Signal Peak

Problem

You are an engineer at a telemetry company. Your system models signal strength across a network as a binary tree — each node has a signal value (can be negative if the node is degrading the signal). You need to find the path through the network that carries the maximum total signal strength.

A path is any sequence of nodes connected by edges. The path must contain at least one node, does not need to pass through the root, and cannot branch (it cannot go left AND right AND up from the same node).

Given a binary tree as a level-order array where null represents a missing node, return the maximum path sum.

Examples

Example 1

Input: [1, 2, 3]

Output: 6

The optimal path is 2→1→3 passing through the root. Sum = 2+1+3 = 6.

Example 2

Input: [-10, 9, 20, null, null, 15, 7]

Output: 42

Root -10 is toxic. Best path is entirely within right subtree: 15→20→7 = 42. Never include the root.

Example 3

Input: [-3, -5, -2]

Output: -2

All nodes negative — must pick the least bad single node (-2). Initializing max to 0 gives wrong answer.

Constraints

›1 <= number of nodes <= 3×10^4
›-1000 <= node.val <= 1000
›null in the input represents a missing node

Loading question…