Given a binary tree, return the vertical order traversal of its nodes values. For each node at position (X, Y), its left and right children respectively will be at positions (X - 1, Y - 1) and (X + 1, Y - 1). Running a vertical line from X = -infinity to X = +infinity, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing Y coordinates). If two nodes have the same position, then the value of the node that is reported first is the value that is smaller. Return an list of non-empty reports in order of X coordinates. Every report will have a list of values of nodes.
// Use HashMap to store X // Use TreeMap to store Y // If some nodes have same (X, Y), they are in the Priority Queue. Map<Integer, TreeMap<Integer, PriorityQueue<Integer>>> map = new HashMap<>(); int minX = 0, maxX = 0;
public List<List<Integer>> verticalTraversal(TreeNode root) { buildMap(root, 0, 0); List<List<Integer>> result = new ArrayList<>(); // For each X for (int x = minX; x <= maxX; ++x) { List<Integer> level = new ArrayList<>(); // For each Y (in order bc TreeMap) for (int y : map.get(x).keySet()) { PriorityQueue<Integer> pq = map.get(x).get(y); while (pq.size () > 0) { level.add(pq.poll()); } } result.add(level); } return result; }
privatevoidbuildMap(TreeNode node, int x, int y){ // traverse each node O(N) if (node == null) { return; } // record min & max minX = Math.min(minX, x); maxX = Math.max(maxX, x); if (map.get(x) == null) { // Init TreeMap map.put(x, new TreeMap<Integer, PriorityQueue<Integer>>()); } if (map.get(x).get(y) == null) { // Init PQ map.get(x).put(y, new PriorityQueue<Integer>()); // O(log(h)) } PriorityQueue<Integer> pq = map.get(x).get(y); pq.add(node.val); // log // recursive helper(node.left, x - 1, y + 1); helper(node.right, x + 1, y + 1); }
Time: $O(N\log{N})$ for each node the runtime could be upper bounded by $O(\log{N})$. Space: $O(N)$
Map<Integer, Map<Integer, PriorityQueue<Integer>>> map; int minX = 0; int maxX = 0;
public List<List<Integer>> verticalTraversal(TreeNode root) { if (root == null) { returnnull; } map = new HashMap<>(); buildMap(root, 0, 0); // Iterate map List<List<Integer>> result = new ArrayList<>(); for (int x = minX; x <= maxX; ++x) { List<Integer> list = new ArrayList<>(); Map<Integer, PriorityQueue<Integer>> treeMap = map.get(x); for (Integer y : treeMap.keySet()) { // in order PriorityQueue<Integer> pq = treeMap.get(y); while (pq.size() > 0) { list.add(pq.poll()); } } result.add(list); } return result; }
privatevoidbuildMap(TreeNode root, int x, int y){ if (root == null) { return; } // root minX = Math.min(minX, x); maxX = Math.max(maxX, x); Map<Integer, PriorityQueue<Integer>> treeMap = map.getOrDefault(x, new TreeMap<>()); PriorityQueue<Integer> pq = treeMap.getOrDefault(y, new PriorityQueue<>()); pq.add(root.val); // set back treeMap.put(y, pq); map.put(x, treeMap); // left buildMap(root.left, x - 1, y + 1); // right buildMap(root.right, x + 1, y + 1); }