Vertical Order Traversal of a Binary Tree
HardP3Coding
Give every node a position (row, col): the root is at (0, 0), a left child of (r, c) is at (r + 1, c - 1) and a right child is at (r + 1, c + 1).
Group nodes by column and return the groups from the leftmost column to the rightmost. Inside a column, order the values by row from top to bottom; if two nodes share both row and column, put the smaller value first.
Example 1
- Input
- root = [3,9,20,null,null,15,7]
- Output
- [[9],[3,15],[20],[7]]
Example 2
- Input
- root = [1,2,3,4,6,5,7]
- Output
- [[4],[2],[1,5,6],[3],[7]]
- Why
- 5 and 6 are both at row 2, column 0, so the smaller value 5 comes first.
Constraints
- 0 <= number of nodes <= 1000
- 0 <= Node.val <= 1000
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 9. ⌘Enter runs, ⌘⇧Enter submits.