[数据结构与算法]力扣 987. 二叉树的垂序遍历

题目来源：https://leetcode-cn.com/problems/vertical-order-traversal-of-a-binary-tree/

大致题意：
题中新定义一种二叉树的遍历方法，垂序遍历。
对于一个位于（row, col）的节点来说，它的左节点为（row+1, col-1），右节点为（row+1, col+1）。
垂序遍历为从左至右，遍历列数（col）相同的节点，相同列按照row升序排列，列行都相同则按照节点值升序排列。
输出类型为相同col的存为一个集合，返回所有col集合的集合。

思路

可知垂序遍历主要依据row、col以及节点值，而不是传统的左右指针。
所以可以遍历存下所有节点的row、col以及节点值，然后按照规则排序，再遍历输出。

dfs + sort

1. dfs遍历所有节点，存下row、col以及节点值入集合
2. 集合排序，自定义排序规则，优先col、其次row、最次节点值
3. 遍历集合，相同col的存入一个集合

代码：

public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<int[]> nodes = new ArrayList<int[]>();
        // 遍历所有节点信息
        dfs(root, 0, 0, nodes);
        // 自定义排序规则
        Collections.sort(nodes, new Comparator<int[]>(){
            public int compare(int[] a, int[] b) {
                if (a[0] != b[0]) {
                    // 优先按照col升序排序
                    return a[0] - b[0];
                }
                else if (a[1] != b[1]) {
                    // 其次按照row升序排序
                    return a[1] - b[1];
                }
                else{
                    // 最后按照节点值升序
                    return a[2] - b[2];
                }
            }
        });
        List<List<Integer>> traversal = new ArrayList<List<Integer>>();
        int col = Integer.MIN_VALUE;
        int index = -1;
        for (int[] node : nodes) {
            int curCol = node[0];
            // 若当前col已经和之前不同
            if (col != curCol) {
                // 更新col
                col = curCol;
                // 添加新列表
                traversal.add(new ArrayList<Integer>());
                // 更新集合下标
                index++;
            }
            // 存入当前节点
            traversal.get(index).add(node[2]);
        }
        return traversal;
    }
    public void dfs(TreeNode node, int row, int col, List<int[]> nodes) {
        if (node == null)
            return;
        // 添加节点信息
        nodes.add(new int[]{col, row, node.val});
        // 递归遍历
        dfs(node.left, row+1, col-1, nodes);
        dfs(node.right, row+1, col+1, nodes);
    }