314 binary tree vertical order traversal

https://leetcode.com/problems/binary-tree-vertical-order-traversal/

关键还是要想到记录col然后整理

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private class Node {
        TreeNode node;
        int col;
        public Node(TreeNode node, int col) {
            this.node = node;
            this.col = col;
        }
    }
    public List<List<Integer>> verticalOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<List<Integer>> ans = new ArrayList<>();
        Queue<Node> queue = new ArrayDeque<>();
        queue.offer(new Node(root, 0));
        Map<Integer, List<Integer>> map = new HashMap<>();
        int minCol = Integer.MAX_VALUE;
        int maxCol = Integer.MIN_VALUE;
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            List<Integer> list = map.get(node.col);
            minCol = Math.min(minCol, node.col);
            maxCol = Math.max(maxCol, node.col);
            if (list == null) {
                list = new ArrayList<>();
            }
            list.add(node.node.val);
            map.put(node.col, list);
            if (node.node.left != null) {
                queue.offer(new Node(node.node.left, node.col - 1));
            }
            if (node.node.right != null) {
                queue.offer(new Node(node.node.right, node.col + 1));
            }
        }
        for (int i = minCol; i <= maxCol; i++) {
            List<Integer> list = map.get(i);
            if (list != null) {
                ans.add(list);
            }
        }
        return ans;
    }
}