Place the root of a binary tree at row 0, column 0. A node at (row, col) has its left child at (row + 1, col - 1) and its right child at (row + 1, col + 1). Return the vertical order traversal: one list per column from the leftmost column to the rightmost. Inside a column, list nodes from top to bottom, and when two nodes share the same row and column, put the smaller value first.
- 1 <= number of nodes <= 1000
- 0 <= Node.val <= 1000
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Trying to build the answer column by column while traversing gets messy, because a plain BFS does not order equal positions by value. The clean idea is to separate collecting from ordering: visit every node once and store (col, row, val). Then a single sort on the triple applies all three rules at once (column first, then row, then value). Finally walk the sorted list and start a new group whenever the column changes.
Algorithm
- Traverse the tree (BFS or DFS) carrying each node's row and column.
- Store a triple
(col, row, val)for every node. - Sort the triples in increasing order.
- Walk the sorted triples and start a new inner list whenever
colchanges.
O(n log n) for the sortSpace: O(n)class Solution: def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]: items = [] # (col, row, val) stack = [(root, 0, 0)] while stack: node, row, col = stack.pop() if node is None: continue items.append((col, row, node.val)) stack.append((node.left, row + 1, col - 1)) stack.append((node.right, row + 1, col + 1)) items.sort() # column, then row, then value res = [] prev_col = None for col, row, val in items: if col != prev_col: # new column starts res.append([]) prev_col = col res[-1].append(val) return res