Untitled
unknown
java
5 months ago
1.8 kB
2
Indexable
import java.util.*; class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } class Solution { // Using TreeMap for ordered keys, and TreeMap with TreeSet for ordered values in sub-maps private Map<Integer, Map<Integer, TreeSet<Integer>>> m = new TreeMap<>(); public List<List<Integer>> verticalTraversal(TreeNode root) { Queue<Tuple> q = new LinkedList<>(); q.offer(new Tuple(root, 0, 0)); // Perform BFS to populate the map with x and y coordinates while (!q.isEmpty()) { Tuple current = q.poll(); TreeNode temp = current.node; int x = current.x; int y = current.y; // Place the value in the nested map structure m.putIfAbsent(x, new TreeMap<>()); m.get(x).putIfAbsent(y, new TreeSet<>()); m.get(x).get(y).add(temp.val); if (temp.left != null) { q.offer(new Tuple(temp.left, x - 1, y + 1)); } if (temp.right != null) { q.offer(new Tuple(temp.right, x + 1, y + 1)); } } // Create the answer list based on the ordered structure of the map List<List<Integer>> ans = new ArrayList<>(); for (Map<Integer, TreeSet<Integer>> map : m.values()) { List<Integer> col = new ArrayList<>(); for (TreeSet<Integer> nodes : map.values()) { col.addAll(nodes); } ans.add(col); } return ans; } } // Helper class for queue items class Tuple { TreeNode node; int x, y; Tuple(TreeNode node, int x, int y) { this.node = node; this.x = x; this.y = y; } }
Editor is loading...
Leave a Comment