Given the root of a binary tree, return the vertical order traversal of its nodes. For each position (col), nodes are ordered top to bottom, then left to right.
Input: root=[3,9,20,null,null,15,7] → Output: [[9],[3,15],[20],[7]]Input: root=[1,2,3,4,5,6,7] → Output: [[4],[2],[1,5,6],[3],[7]]
DFS collecting (col, row, val) triples. Sort by col, then row, then val. Group by column.
- DFS: dfs(node, col, row) collects (col, row, val).
- Sort list by (col, row, val).
- Group consecutive same-col entries into sublists.
import java.util.*;
class Solution {
List<int[]> nodes = new ArrayList<>();
public List<List<Integer>> verticalTraversal(TreeNode root) {
dfs(root, 0, 0);
nodes.sort((a, b) -> a[0] != b[0] ? a[0]-b[0] : a[1] != b[1] ? a[1]-b[1] : a[2]-b[2]);
List<List<Integer>> result = new ArrayList<>();
int prevCol = Integer.MIN_VALUE;
for (int[] node : nodes) {
if (node[0] != prevCol) { result.add(new ArrayList<>()); prevCol = node[0]; }
result.get(result.size()-1).add(node[2]);
}
return result;
}
private void dfs(TreeNode node, int col, int row) {
if (node == null) return;
nodes.add(new int[]{col, row, node.val});
dfs(node.left, col-1, row+1); dfs(node.right, col+1, row+1);
}
}
- Time Complexity: O(N log N)
- Space Complexity: O(N)