# 0314. Binary Tree Vertical Order Traversal
###### tags: `Leetcode` `FaceBook` `Medium` `BFS`
Link: https://leetcode.com/problems/binary-tree-vertical-order-traversal/
## Code
为了保证顺序，只能用BFS,不能用DFS
### BFS

class Solution {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> output = new ArrayList<>();
        if(root == null) return output;
        Map<Integer, ArrayList> map = new HashMap<>();
        Queue<Pair<TreeNode,Integer>> q = new LinkedList<>();
        int column = 0;
        q.offer(new Pair(root, 0));
        int minColumn = 0, maxColumn = 0;
        while(!q.isEmpty()){
            Pair<TreeNode, Integer> curr = q.poll();
            root = curr.getKey();
            column = curr.getValue();
            
            if(!map.containsKey(column)){
                map.put(column, new ArrayList<Integer>());
            }
            map.get(column).add(root.val);
            
            if(root.left != null){
                q.offer(new Pair(root.left, column-1));
                minColumn = Math.min(minColumn, column-1);
            }
            if(root.right != null){
                q.offer(new Pair(root.right, column+1));
                maxColumn = Math.max(maxColumn, column+1);
            }
        }
        
        for(int i = minColumn;i <= maxColumn;i++){
            output.add(map.get(i));
        }
        return output;
    }
}