Loading...
Given the root of a binary tree, return the largest possible sum of node values over all paths.
A path is a sequence of nodes in which consecutive nodes are connected by an edge, and no node appears more than once. A path can start and end anywhere in the tree, so it does not have to pass through the root, and it must contain at least one node.
Your function receives root as a TreeNode; the node type is provided for you, with val, left and right fields.
The examples below write the tree as its level-order traversal, where null marks a missing child of a listed node and trailing nulls are omitted. That is only how the input is displayed; the decoding is done for you.
Node.val ≤1000The path 2 -> 1 -> 3 uses all three nodes: 2 + 1 + 3 = 6.
The best path is 15 -> 20 -> 7 with sum 42. Extending it up through -10 would only lower the sum.
Click "Run" to test with sample cases or "Submit" to run all tests.