849. Maximum Path Sum Root to Leaf

Given the root of a binary tree, return the maximum sum of node values along any path from the root down to a leaf. An empty tree has sum 0. The tree is given as a level-order array with null for missing children.

Input: A level-order array of the tree.

Output: Integer — the maximum root-to-leaf path sum.

Examples

Input: [1,2,3,4,5,null,6]
Output: 10
Explanation: Path 1-3-6 sums to 10.

Input: [1]
Output: 1
Explanation: Single node.

Input: []
Output: 0
Explanation: Empty tree.

Constraints

• 0<=nodes<=10^4
• -1000<=value<=1000

Asked by