Binary Tree Columns

Given the root of a binary tree, group the values of the nodes by vertical column, and return the columns ordered from leftmost to rightmost. Within a column, values should be ordered top to bottom by level; if two nodes land in the same column and the same level, order them left to right.

Column index is defined relative to the root, which is at column 0: moving to a left child decreases the column index by 1, and moving to a right child increases it by 1.

Example 1

Input: [3, 9, 20, null, null, 15, 7]

      3
     / \
    9  20
       / \
      15  7

Columns: 9 is at column -1, 3 and 15 are at column 0, 20 is at column 1, 7 is at column 2.

Output: [[9], [3, 15], [20], [7]].

Example 2

Input: [3, 9, 8, 4, 0, 1, 7]

          3
        /   \
       9     8
      / \   / \
     4   0 1   7

Output: [[4], [9], [3, 0, 1], [8], [7]] — node 0 (column 0, level 2) and node 3 (column 0, level 1) share column 0; 3 comes first because it's a shallower level, and 1 (also column 0, level 2) comes after 0 because it's to the right of 0 at the same level.

Constraints

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