Draw a binary tree so that the root sits in column 0, every left child one column to the
left of its parent (column - 1) and every right child one column to the right
(column + 1). Given the root, return the sum of the values in each column, listed from the
leftmost column to the rightmost. Return [] for an empty tree.
Examples
1
/ \
2 3
/ \ \
4 5 6
Input: root = build_tree([1, 2, 3, 4, 5, None, 6])
Output: [4, 2, 6, 3, 6]
Explanation: columns -2..2 hold {4}, {2}, {1, 5}, {3}, {6}.
3
/ \
9 20
/ \
15 7
Input: root = build_tree([3, 9, 20, None, None, 15, 7])
Output: [9, 18, 20, 7]
Explanation: 3 and 15 share column 0.
Constraints
0 <= number of nodes <= 2000-10**4 <= node.val <= 10**4- Target complexity: O(n) time.
Goals
- Assign a horizontal column index to every node
- Aggregate values per column with a dictionary
- Output columns in left-to-right order