Largest Root to Leaf Sum

Given the root to a binary tree root, return the largest sum of any path that goes from the root to a leaf.

Constraints

• n ≤ 100,000 where n is the number of nodes in root

https://binarysearch.com/problems/Largest-Root-to-Leaf-Sum

Examples

Example 1

Input

• root =

Output

• answer = 20

Explanation

The path with the largest sum is 1 -> 4 -> 7 -> 8

Solution