987. 二叉树的垂序遍历

approach 1

class Solution {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<int[]> ns = new ArrayList<>();
        dfs(root, 0, 0, ns);
        Collections.sort(ns, (a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            }
            if (a[1] != b[1]) {
                return a[1] - b[1];
            }
            return a[2] - b[2];
        });

        List<List<Integer>> res = new ArrayList<>();
        int lc = -9999;
        for (int i = 0; i < ns.size(); i++) {
            int[] n = ns.get(i);
            if (n[0] != lc) {
                res.add(new ArrayList<>());
                lc = n[0];
            }
            res.get(res.size()-1).add(n[2]);
        }

        return res;
    }

    private void dfs(TreeNode node, int r, int c, List<int[]> ns) {
        if (node == null) return;

        ns.add(new int[]{c, r, node.val});
        dfs(node.left, r+1, c-1, ns);
        dfs(node.right, r+1, c+1, ns);
    }
}