Sum of the Deepest Nodes

Given a binary tree root, find the sum of the deepest node values.

Constraints

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

https://binarysearch.com/problems/Sum-of-the-Deepest-Nodes

Examples

Example 1

Input

• root =

Output

• answer = 6

Explanation

Since values 4 and 2 are deepest.

Example 2

Input

• root =

Output

• answer = 3

Explanation

Since 3 is deepest.

Solution