987 verticle order traversal of a binary tree

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

跟314很像。用dfs的话需要注意每个col里数的顺序，往上的排前面，同一层的按照val排列

/**
 * 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 {
        int val;
        int row;
        public Node(int v, int r) {
            val = v;
            row = r;
        }
    }
    private TreeMap<Integer, List<Node>> map = new TreeMap<>();
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        traverse(root, 0, 0);
        List<List<Integer>> ans = new ArrayList<>();
        for (List<Node> nodes : map.values()) {
            nodes.sort(new Comparator<Node>() {
                @Override
                public int compare(Node n1, Node n2) {
                    if (n1.row == n2.row) {
                        return n1.val - n2.val;
                    }
                    return n1.row - n2.row;
                }
            });
            List<Integer> seg = new ArrayList<>();
            for (Node node : nodes) {
                seg.add(node.val);
            }
            ans.add(seg);
        }
        return ans;
    }
    private void traverse(TreeNode root, int col, int row) {
        if (root == null) return;
        List<Node> list = map.get(col);
        if (list == null) list = new ArrayList<>();
        list.add(new Node(root.val, row));
        map.put(col, list);
        traverse(root.left, col - 1, row + 1);
        traverse(root.right, col + 1, row + 1);
    }
}