Mid/Senior
Binary Tree Vertical Order Traversal
Given the root of a binary tree, return the vertical order traversal of its nodes' values.
For each node at position (row, col):
- The root is at
(0, 0). - The left child of a node at
(row, col)is at(row + 1, col - 1). - The right child of a node at
(row, col)is at(row + 1, col + 1).
Return the values column by column from the leftmost column to the rightmost column. Within each column, nodes should appear from top to bottom. If two nodes are in the same row and column, they should appear in left-to-right order as they are encountered in the tree.
Example 1
3
/ \
9 20
/ \
15 7Input
root = [3,9,20,null,null,15,7]Output
[[9],[3,15],[20],[7]]Column -1 contains 9, column 0 contains 3 then 15, column 1 contains 20, and column 2 contains 7.
Example 2
3
/ \
9 8
/ \ / \
4 0 1 7Input
root = [3,9,8,4,0,1,7]Output
[[4],[9],[3,0,1],[8],[7]]Reading columns from left to right gives 4, then 9, then 3, 0, and 1, then 8, then 7.
Constraints
- 0 <= number of nodes <= 100
- -100 <= Node.val <= 100