# 0987. Vertical Order Traversal of a Binary Tree
###### tags: `Leetcode` `Hard` `Bloomberg` `BFS` `DFS`
Link: https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/
## 思路
和[314. Binary Tree Vertical Order Traversal](https://hackmd.io/ED-7DCHkQByRQaHGr6ETWw)有点像，区别在于需不需要按node value大小排序

原本的想法是用Map<Integer, List<Pair<Integer, Integer>>收集每个col对应的treenode的val，以及他们对应的row number，如果一个新的pair加进来，它和上一个的row number一样，就给他们两个排序，但是忽略了一个问题是 **如果tree比较深的话，有可能同一个row number 同一个col number对应的TreeNode有好几个**，而不是两个，所以只能在收集好他们之后，把他们存进答案之前，给他们排序

### 方法二 top voted方法
在层序遍历每层的时候建一个map，存col值和node value的对应，然后排序，因为这样产生的一个list里面一定是col值和row值都相等的node，之后再放到以col值为key的map里面，最后再用之前vertical order traversal的方法遍历即可
## Code
### 方法一

class Solution {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        //node.val row
        Map<Integer, List<Pair<Integer, Integer>>> map = new HashMap<>();
        Queue<Pair<TreeNode, Pair<Integer,Integer>>> q = new LinkedList<>();
        int minCol = Integer.MAX_VALUE, maxCol = Integer.MIN_VALUE;
        q.add(new Pair<>(root, new Pair<Integer, Integer>(0,0)));
        while(!q.isEmpty()){
            Pair<TreeNode, Pair<Integer, Integer>> curr = q.poll();
            TreeNode currNode = curr.getKey();
            int row = curr.getValue().getKey();
            int col = curr.getValue().getValue();
            
            if(!map.containsKey(col)){
                map.put(col, new ArrayList<Pair<Integer, Integer>>());
            }
            
            map.get(col).add(new Pair<>(currNode.val, row));  
            
            minCol = Math.min(minCol, col);
            maxCol = Math.max(maxCol, col);
            
            if(currNode.left!=null){
                q.offer(new Pair(currNode.left, new Pair(row+1, col-1)));
            }
            if(currNode.right!=null){
                q.offer(new Pair(currNode.right, new Pair(row+1, col+1)));
            }
        }
        
        List<List<Integer>> ans = new ArrayList<>();
        for(int i = minCol; i <= maxCol;i++){
            
            Collections.sort(map.get(i), new Comparator<Pair<Integer,Integer>>(){
                
                public int compare(Pair<Integer, Integer> p1, Pair<Integer, Integer> p2){
                    if(p1.getValue().equals(p2.getValue())){
                        return p1.getKey()-p2.getKey();
                    }
                    else{
                        return p1.getValue()-p2.getValue();
                    }
                }
            });
            List<Integer> sorted = new ArrayList();
            for(Pair<Integer, Integer> p:map.get(i)){
                sorted.add(p.getKey());
            }
            ans.add(sorted);
        }
        return ans;
    }
}

### 方法二

class Solution {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        Map<Integer, List<Integer>> colMap = new HashMap<>();
        Queue<Pair<TreeNode,Integer>> q = new LinkedList<>();
        q.add(new Pair<>(root,0));
        int minCol = 0;
        int maxCol = 0;
        while(!q.isEmpty()){
            int size = q.size();
            Map<Integer, List<Integer>> tmpMap = new HashMap<>();
            for(int i = 0;i < size;i++){
                Pair<TreeNode, Integer> curr = q.poll();
                TreeNode currNode = curr.getKey();
                int col = curr.getValue();
                minCol = Math.min(col, minCol);
                maxCol = Math.max(col, maxCol);
                if(!tmpMap.containsKey(col)) tmpMap.put(col, new ArrayList<>());
                tmpMap.get(col).add(currNode.val);
                if(currNode.left!=null) q.add(new Pair<>(currNode.left, col-1));
                if(currNode.right!=null) q.add(new Pair<>(currNode.right, col+1));
            }
            for(int key:tmpMap.keySet()){
                if(!colMap.containsKey(key)){
                    colMap.put(key, new ArrayList<>());
                }
                List<Integer> temp = tmpMap.get(key);
                Collections.sort(temp);
                colMap.get(key).addAll(temp);
            }
        }
        
        List<List<Integer>> ans = new ArrayList<>();
        for(int i = minCol;i <= maxCol;i++){
            ans.add(colMap.get(i));
        }
        return ans;
    }
}