Longest Tree Sum Path From Root to Leaf

Given a binary tree root, return the sum of the longest path from the root to a leaf node. If there are two equally long paths, return the larger sum.

Constraints

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

https://binarysearch.com/problems/Longest-Tree-Sum-Path-From-Root-to-Leaf

Examples

Example 1

Input

• root =

Output

• answer = 18

Explanation

The longest path here is 5 nodes long: 1 -> 4 -> 7 -> 4 -> 2.

Solution