Diagonal Tree Traversal

Given a binary tree root, return the sum of each of the diagonals in the tree starting from the top to bottom right.

Constraints

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

https://binarysearch.com/problems/Diagonal-Tree-Traversal

Examples

Example 1

Input

• root =

Output

• answer = [6, 15, 7]

Explanation

The diagonals are:

1 -> 2 -> 3
4 -> 5 -> 6
7

Example 2

Input

• root =

Output

• answer = [4, 2]

Solution