NeetCode #399LC-314MediumTreesNC Algo100
← Back to All Problems#399 · #314 · Binary Tree Vertical Order Traversal(二叉树的垂序遍历)
📌 Problem Statement & Constraints
Given the root of a binary tree, return its vertical order traversal: a list of columns from leftmost to rightmost, where each column lists the node values top to bottom. Within a column, nodes at the same depth are ordered left to right. Constraints: the number of nodes is in
[0, 1000].💡 Core Algorithmic Approaches
- Assign each node a column index: the root is 0, the left child is
column - 1, the right childcolumn + 1. - BFS is essential here, because it guarantees that nodes are appended in top-to-bottom order, and left-to-right within the same depth.
- Collect the values into a map from column to list, then emit the columns in ascending order.
- A DFS would need an extra sort key of
(depth, order)to reproduce the same ordering.
💻 Benchmark Python3 Implementation
class Solution:
def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
from collections import defaultdict, deque
if not root:
return []
cols = defaultdict(list)
q = deque([(root, 0)]) # (node, column)
while q:
node, c = q.popleft()
cols[c].append(node.val)
if node.left:
q.append((node.left, c - 1))
if node.right:
q.append((node.right, c + 1))
return [cols[c] for c in sorted(cols)]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n + w log w) where w is the number of distinct columns: the BFS is linear and the final sort is over the columns.
💾 Space Complexity
O(n) for the map and the queue.
⚠️ Interview Pitfalls & Follow-ups
- Using DFS: it does not guarantee top-to-bottom ordering within a column; you would need to sort by depth and then by traversal order.
- Forgetting to sort the columns: the map's key order is insertion order, not left-to-right.
- Using a list indexed by column with an offset: it works, but the range of columns is unknown up front, making a dict safer.
- Appending children in the wrong order: left must be pushed before right so the left-to-right tie-break holds.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.