Practice/Meta/Leetcode 987. Vertical Order Traversal of a Binary Tree

Leetcode 987. Vertical Order Traversal of a Binary Tree

CodingMust

Problem

Given the root of a binary tree, compute a column-based representation of the tree where each node is assigned a coordinate pair (row, column).

The root node starts at position (0, 0). For any node at position (r, c):

• Its left child is located at (r + 1, c - 1)
• Its right child is located at (r + 1, c + 1)

Return a list of lists where each inner list represents one column of the tree, ordered from the leftmost column to the rightmost column. Within each column, nodes should be ordered by:

1. Increasing row number (top to bottom)
2. For nodes at the same row and column, by increasing node value

Requirements

1. Traverse the tree and assign coordinates to each node
2. Group nodes by their column index
3. Sort nodes within each column first by row, then by value for ties
4. Return columns in left-to-right order

Constraints

• The number of nodes in the tree is in the range [1, 1000]
• 0 ≤= Node.val ≤= 1000
• You must handle cases where multiple nodes occupy the same (row, column) position

Examples

Example 1:

Input: root = [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 Output: [[9],[3,15],[20],[7]] Explanation: Column -1: node 9 at (1, -1) Column 0: nodes 3 at (0, 0) and 15 at (2, 0) Column 1: node 20 at (1, 1) Column 2: node 7 at (2, 2)

Example 2:

Input: root = [1,2,3,4,5,6,7] 1 / \ 2 3 / \ / \ 4 5 6 7 Output: [[4],[2],[1,5,6],[3],[7]] Explanation: Column -2: node 4 at (2, -2) Column -1: node 2 at (1, -1) Column 0: nodes 1 at (0, 0), 5 at (2, 0), 6 at (2, 0) - sorted as [1,5,6] Column 1: node 3 at (1, 1) Column 2: node 7 at (2, 2)

Example 3:

Input: root = [1,2,3,4,6,5,7] Output: [[4],[2],[1,5,6],[3],[7]] Explanation: This is similar to Example 2, but notice that nodes 5 and 6 both exist at position (2, 0), so they must be sorted by value.