my concise Java solution using treemap and queue


  • 0
    D
    public class Solution {
        public class Pair {
            TreeNode node;
            int index;
            public Pair(TreeNode node, int index) {
                this.node = node;
                this.index = index;
            }
        }
        public List<List<Integer>> verticalOrder(TreeNode root) {
            List<List<Integer>> res = new ArrayList<>();
            if (root == null) return res;
            Queue<Pair> q = new LinkedList<>();
            Map<Integer, List<Integer>> map = new TreeMap<>();        
            q.offer(new Pair(root, 0));
    
            while (!q.isEmpty()) {
                Pair p = q.poll();
                map.putIfAbsent(p.index, new ArrayList<Integer>());
                map.get(p.index).add(p.node.val);
                if (p.node.left != null) q.offer(new Pair(p.node.left, p.index - 1));
                if (p.node.right != null) q.offer(new Pair(p.node.right, p.index + 1));
            }
            
            for (int key : map.keySet()) res.add(map.get(key));
            return res;
        }
    }

Log in to reply
 

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