My Java TreeMap with BFS solution


  • 0
    class Pair {
        TreeNode x;
        int y;
        Pair (TreeNode x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public class Solution {
        public List<List<Integer>> verticalOrder(TreeNode root) {
            List<List<Integer>> res = new ArrayList<>();
            if (root == null) {
                return res;
            }
            TreeMap<Integer, List<Integer>> map = new TreeMap<>();
            LinkedList<Pair> queue = new LinkedList<>();
            queue.add(new Pair(root, 0));
            
            while (!queue.isEmpty()) {
                Pair pair = queue.poll();
                List<Integer> list;
                if (!map.containsKey(pair.y)) {
                    list = new ArrayList<>();
                }
                else {
                    list = map.get(pair.y);
                }
                list.add(pair.x.val);
                map.put(pair.y, list);
                
                if (pair.x.left != null) {
                    queue.add(new Pair(pair.x.left, pair.y - 1));
                }
                if (pair.x.right != null) {
                    queue.add(new Pair(pair.x.right, pair.y + 1));
                }
            }
            
            res.addAll(map.values());
            return res;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.