[数据结构与算法]leetcode每日一题987. 二叉树的垂序遍历20210731

987. 二叉树的垂序遍历

题目：

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

答案

class Solution {
    // key -> col, value -> key->row,value->node.val
    Map<Integer, Map<Integer, List<Integer>>> map = new HashMap<>();
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        dfs(root, 0, 0);
        // 组装
        return map.keySet().stream().sorted().map(col -> {
                List<Integer> rowList = new ArrayList<>();
                map.get(col).keySet().stream().sorted().forEach(row -> {
                    List<Integer> value = map.get(col).get(row);
                    Collections.sort(value);
                    rowList.addAll(value);
                });
                return rowList;
            }).collect(Collectors.toList());
    }

    // 深度优先遍历 
    private void dfs(TreeNode node, int row, int col) {
        if(node == null) {
            return;
        }
        map.computeIfAbsent(col, rowMap -> new HashMap<>())
        .computeIfAbsent(row, list -> new ArrayList<>()).add(node.val);
        dfs(node.left, row+1, col-1);
        dfs(node.right, row+1, col+1);
    }
}

总结

一遍过，无debug

dfs循环到每一个节点，存储到map中。
最后组装map。