All problems

Slanted Sunbeams

Medium · tree dfs

A glasshouse hangs its planters in a binary tree: the top planter is the root, and every planter has at most two planters hanging below it, one to the left and one to the right. The number on a planter is how many flowers it holds.

Every morning the sun shines in at a slant, in parallel sunbeams. A beam lights a planter, then carries on down to that planter's right child, then that child's right child, and so on until there are no more right children. A left child is not on its parent's beam: it sits on the next beam over.

So the root and its chain of right children are on beam 0. The left children of the planters on beam 0, together with their own chains of right children, are on beam 1. The left children of the planters on beam 1 start beam 2, and so on.

Return a list with the total number of flowers on each beam, beam 0 first. For an empty tree, return an empty list.

Examples

Example 1

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

Output: [10, 7, 4]

Beam 0 lights 1, 3 and 6. Beam 1 lights 2 and 5, and beam 2 lights 4 on its own.

Example 2

Input: root = [5, null, 8, null, 2]

Output: [15]

Every planter is a right child, so a single beam lights all of them.

Example 3

Input: root = [3, 1, null, 7, null, 4]

Output: [3, 1, 7, 4]

Every planter is a left child, so each one is alone on its own beam.

Constraints