Level Sums Zigzag

Easy · tree bfs

You are given the root of a binary tree. Return one number for each level of the tree, from the top level down. Number the levels from 0, so the root is on level 0, its children are on level 1, and so on.

How the number for a level is worked out depends on the level:

On an even level (0, 2, 4, ...), it is the plain sum of the values on that level.
On an odd level (1, 3, 5, ...), read the values from right to left as v1, v2, v3, ..., so v1 is the rightmost value, and take the alternating total v1 - v2 + v3 - v4 + ....

A level with a single value is just that value. An empty tree has no levels, so return [].

Examples

Example 1

Input: root = [5, 2, 7, 4, 1, 3, 6]

Output: [5, 5, 14]

Level 0 is 5. Level 1 is odd and reads 7, 2 from the right, so 7 - 2 = 5. Level 2 is even: 4 + 1 + 3 + 6 = 14.

Example 2

Input: root = [1, 2, 3, 4, 5, null, 6, 7, 8, 9]

Output: [1, 1, 15, 8]

Level 1 reads 3, 2 from the right: 3 - 2 = 1. Level 2 is 4 + 5 + 6 = 15. Level 3 is odd and reads 9, 8, 7 from the right: 9 - 8 + 7 = 8.

Example 3

Input: root = []

Output: []

There are no levels, so there are no numbers.

Constraints

The number of nodes is in the range [0, 1000].
-1000 <= Node.val <= 1000