481. Column by Column
A conference hall hangs posters on a wall following the shape of a binary tree. The root poster is at column 0 and row 0. Moving to a left child shifts one column to the left and one row down, and moving to a right child shifts one column to the right and one row down. Given the tree in root, a visitor reads the posters column by column, starting at the leftmost column and ending at the rightmost one.
Return a two-dimensional array in which each inner array holds the values of one column. Inside a column, the values are listed from the top row to the bottom row; when two nodes share both the same column and the same row, the smaller value comes first. Only columns that contain at least one node appear in the result. For an empty tree return an empty array.
Example 1
- Input:
- root = [3,1,4,0,2,null,6,null,null,null,null,5]
- Output:
- [[0],[1],[3,2],[4,5],[6]]
- Explanation:
Columns from left to right hold [0], [1], [3, 2], [4, 5] and [6]; in the middle column 3 is on row 0 and 2 on row 2.
Example 2
- Input:
- root = [9,4,6,null,8,3]
- Output:
- [[4],[9,3,8],[6]]
- Explanation:
Nodes 8 and 3 share column 0 and row 2, so the smaller value 3 comes first, after the root 9.
Example 3
- Input:
- root = [5]
- Output:
- [[5]]
- Explanation:
A single node forms a single column.
Constraints
0 ≤ number of nodes ≤ 105
-1000 ≤ Node.val ≤ 1000 (values may repeat)
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)