Java coding using BFS and TreeMap


  • 3
    Y
    public class Solution {
        public List<List<Integer>> verticalOrder(TreeNode root) {
            List<List<Integer>> res = new ArrayList<>();
            if(root == null) {
                return res;
            }
            Map<Integer, List<Integer>> map = new TreeMap<>();
            Queue<Integer> qCol = new LinkedList<>();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            qCol.offer(0);
            
            while(!queue.isEmpty()) {
                TreeNode curr = queue.poll();
                int col = qCol.poll();
                if(!map.containsKey(col)) {
                    map.put(col, new ArrayList<Integer>(Arrays.asList(curr.val)));
                } else {
                    map.get(col).add(curr.val);
                }
                if(curr.left != null) {
                    queue.offer(curr.left);
                    qCol.offer(col - 1);
                }
                if(curr.right != null) {
                    queue.offer(curr.right);
                    qCol.offer(col + 1);
                }
            }
            for(int n : map.keySet()) {
                res.add(map.get(n));
            }
            return res;
        }
    }

Log in to reply
 

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