Return the vertical order traversal of a binary tree as columns of node values from left to right.
Given the root of a binary tree, perform a vertical order traversal. Nodes are grouped by their horizontal distance from the root. A node's column is determined by the sum of left moves (-1) and right moves (+1) from the root.
Return a list of lists where each inner list contains node values from top to bottom for each column, ordered from leftmost column to rightmost.
Examples
Input:[3,9,20,null,null,15,7]
Output:
Input:[3,9,8,4,0,1,7]
Output:
Hints
Use BFS and track the column index for each node.
Group nodes by their column index.
Sort columns and then sort nodes within each column by row.