二叉树的垂序遍历

/* 
 思路：
 1. 使用DFS遍历二叉树，每个节点跟踪其行(row)和列(col)。
 2. 使用Map存储列索引到节点值的映射，列索引作为键，值是一个包含(row, node.val)的List。
 3. 对每个节点，插入到相应列索引的List中。
 4. 遍历Map的每个条目，提取节点值，并按(row, node.val)排序，最后使用Stream进行处理。
*/

import java.util.*;
import java.util.stream.Collectors;

public class VerticalOrderTraversalStream {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val) { this.val = val; }
    }

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        Map<Integer, List<int[]>> map = new HashMap<>();
        dfs(root, 0, 0, map);
        return map.entrySet().stream()
                .sorted(Map.Entry.comparingByKey())
                .map(entry -> entry.getValue().stream()
                        .sorted((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0])
                        .map(a -> a[1])
                        .collect(Collectors.toList()))
                .collect(Collectors.toList());
    }

    private void dfs(TreeNode node, int row, int col, Map<Integer, List<int[]>> map) {
        if (node == null) return;
        map.computeIfAbsent(col, k -> new ArrayList<>()).add(new int[]{row, node.val});
        dfs(node.left, row + 1, col - 1, map);
        dfs(node.right, row + 1, col + 1, map);
    }
}