Problem

At Meta, you may need to aggregate tree-structured data by vertical alignment. Given the root of a binary tree, return the sum of node values in each vertical column from leftmost column to rightmost column.

A node's column index is defined relative to the root:

• The root is in column 0
• The left child of a node in column c is in column c - 1
• The right child of a node in column c is in column c + 1

Formal Specification

Implement a function:

• Input: root, the root node of a binary tree, or null for an empty tree
• Output: A list of integers where each value is the sum of all node values in one vertical column, ordered from smallest column index to largest

Examples

Example 1 Input: root = [1,2,3,4,5,6,7] Output: [4,2,12,3,7] Explanation: Columns are -2:[4], -1:[2], 0:[1,5,6], 1:[3], 2:[7].

Example 2 Input: root = [3,9,20,null,null,15,7] Output: [9,18,20,7] Explanation: Columns are -1:[9], 0:[3,15], 1:[20], 2:[7].

Constraints

• The number of nodes is in the range [0, 10^5]
• -10^4 <= node.val <= 10^4
• The tree may be unbalanced
• Return an empty list for an empty tree