912. Vertical Order Traversal (Coordinate Sort)

Given the root of a binary tree, return its vertical order traversal. Assign the root coordinates (row 0, col 0); a left child is (row+1, col-1) and a right child (row+1, col+1). Group values by column left to right; within a column order by row, and for equal (row, col) order by value. Return the result as a nested array. The tree is given as a level-order array.

Input: A level-order array of the tree.

Output: Nested array — values grouped by column, coordinate-sorted.

Examples

Input: [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation: Columns left to right.

Input: [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation: Overlapping nodes sorted by value.

Input: []
Output: []
Explanation: Empty tree.

Constraints

• 0<=nodes<=1000
• 0<=value<=1000

Asked by