Given the root of a binary tree, return its vertical order traversal.
Give each node a position (row, col). The root is at (0, 0). A left child of a node at (row, col) is at (row + 1, col - 1). A right child is at (row + 1, col + 1).
Group the nodes by column and go from the leftmost column to the rightmost column. Inside a column, list the nodes from top to bottom (smaller row first). If two nodes are in the same row and the same column, put the one with the smaller value first.
Return a list that has one list of values for each column.
How the judge passes the data
Examples
Example 1:
Input: root = [5,3,8,1,null,7,9]
Output: [[1],[3],[5,7],[8],[9]]
Explanation: Column -2 has 1. Column -1 has 3.
Column 0 has 5 (at the top) and then 7 (two rows below).
Column 1 has 8. Column 2 has 9.
Example 2:
Input: root = [6,2,9,null,4,3]
Output: [[2],[6,3,4],[9]]
Explanation: Column 0 has 6 at row 0. It also has 3 and 4, both at row 2.
They share the same row, so the smaller value 3 comes first.
Example 3:
Input: root = [10,5,15]
Output: [[5],[10],[15]]
Explanation: Each column has only one node.