Sponsored
Sponsored
This approach uses a Breadth-First Search (BFS) to traverse the tree while tracking each node's position (row, col). We use a queue to manage our BFS process, which stores tuples of (node, row, col). As we visit each node, we place it into a list corresponding to its column index. Finally, we sort each column by first row, then value, and construct the result.
Time Complexity: O(N log N) due to sorting, where N is the number of nodes.
Space Complexity: O(N) for the storage of node values, where N is the number of nodes.
1import java.util.*;
2
3public class Solution {
4 class NodeInfo {
5 TreeNode node;
6 int row;
7 int col;
8
9 public NodeInfo(TreeNode node, int row, int col) {
10 this.node = node;
11 this.row = row;
12 this.col = col;
13 }
14 }
15
16 public List<List<Integer>> verticalOrderTraversal(TreeNode root) {
17 if (root == null) return new ArrayList<>();
18
19 Map<Integer, List<int[]>> columnTable = new HashMap<>();
20 Queue<NodeInfo> queue = new LinkedList<>();
21 int minCol = 0, maxCol = 0;
22
23 queue.offer(new NodeInfo(root, 0, 0));
24
25 while (!queue.isEmpty()) {
26 NodeInfo ni = queue.poll();
27 TreeNode node = ni.node;
28 int row = ni.row, col = ni.col;
29
30 if (!columnTable.containsKey(col)) columnTable.put(col, new ArrayList<>());
31 columnTable.get(col).add(new int[]{row, node.val});
32
33 minCol = Math.min(minCol, col);
34 maxCol = Math.max(maxCol, col);
35
36 if (node.left != null) queue.offer(new NodeInfo(node.left, row + 1, col - 1));
37 if (node.right != null) queue.offer(new NodeInfo(node.right, row + 1, col + 1));
38 }
39
40 List<List<Integer>> result = new ArrayList<>();
41 for (int col = minCol; col <= maxCol; col++) {
42 List<int[]> list = columnTable.get(col);
43 list.sort((a, b) -> a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));
44 List<Integer> currentColumn = new ArrayList<>();
45 for (int[] entry : list) {
46 currentColumn.add(entry[1]);
47 }
48 result.add(currentColumn);
49 }
50
51 return result;
52 }
53}In this solution, a queue stores node information, including node reference, row, and column indices, for BFS processing. As nodes are processed, they are organized in a map by column index. Nodes in each column are sorted by row and node value to produce the final output.
This method involves performing a pre-order traversal (DFS) to collect all nodes along with their column and row indices. Once collected, nodes are sorted based on their columns first, then their rows, and finally their values. The sorted list is then grouped into lists according to their column indices to produce the final vertical order traversal.
Time Complexity: O(N log N) due to sorting, where N is the total number of nodes.
Space Complexity: O(N) to store all the nodes along with their positions.
1import java.util.*;
2
Here, a recursive DFS function appends nodes with respective column and row indices into a list. After traversal, the list is sorted based on col, and row, followed by the value. The sorted nodes are then grouped and collected into the final result output based on column indices.