关注文末推广名片，即可免费获得本题测试源码！

题目来源：🔒LeetCode314：二叉树的垂直遍历

问题抽象： 给定一个二叉树的根节点 root，要求按照 垂直顺序 遍历树的所有节点（即按列从左到右、同列内按行从上到下），并返回节点值的列表序列，满足以下核心需求：

1. 遍历规则定义：

   • 垂直位置：根节点位置为 (0,0)，左子节点位置 (行+1, 列-1)，右子节点位置 (行+1, 列+1)；
   • 输出顺序：
     • 主序：按列号 升序排列（从左至右）；
     • 次序：同列内按行号 升序排列（从上至下）；
     • 同行同列：若多个节点位置相同（行、列均相同），按节点值 升序排列（LeetCode 987 要求，但 314 通常无此要求，按输入顺序即可）。

2. 输出要求：

   • 返回一个列表的列表：[[列1节点值序列], [列2节点值序列], ...]；
   • 每列内的节点值按行顺序从上到下排列（同列同行节点按值升序或任意顺序，题目未强制要求）。

3. 计算约束：

   • 节点数 0 ≤ n ≤ 100；
   • 时间复杂度 O(n log n)（BFS/DFS遍历+排序）；
   • 空间复杂度 O(n)（存储节点位置及队列/递归栈）。

4. 边界处理：

   • 空树：返回空列表 []；
   • 单节点树：输出 [[root.val]]；
   • 偏斜树：如左斜树，所有节点列号递减，但列内仍按行排序；
   • 位置重叠：如节点 A（左子）和 B（右子）同处 (1,0)（需额外处理顺序）。

输入：二叉树根节点 root（节点含 val, left, right）
输出：垂直遍历的节点值列表序列（二维整数列表）。

解题思路

1. 核心目标：按列从左到右收集节点，同列节点按从上到下、从左到右排序。
2. 关键问题：如何确定节点的列索引？
   • 根节点列索引为 0。
   • 左子节点列索引 = 父节点列索引 -1。
   • 右子节点列索引 = 父节点列索引 +1。
3. 算法选择：
   • BFS（广度优先搜索）：层序遍历天然保证从上到下的顺序，同层节点按从左到右处理。
   • 数据结构：
     • 队列 Queue：存储 (节点, 列索引)。
     • 哈希表 HashMap<Integer, List<Integer>>：映射列索引 → 节点值列表。
     • 变量 minCol/maxCol：记录列索引范围，避免最后排序。

时间复杂度：O(N)（每个节点访问一次）。空间复杂度：O(N)（队列和哈希表存储所有节点）。

代码实现（Java版）🔥点击下载源码

class Solution {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        // 列索引 → 节点值列表
        Map<Integer, List<Integer>> colMap = new HashMap<>();
        // 队列存储 (节点, 列索引)
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair<>(root, 0));
        int minCol = 0, maxCol = 0; // 记录列索引范围

        while (!queue.isEmpty()) {
            Pair<TreeNode, Integer> pair = queue.poll();
            TreeNode node = pair.getKey();
            int col = pair.getValue();

            // 将节点值加入对应列的列表
            colMap.computeIfAbsent(col, k -> new ArrayList<>()).add(node.val);
            minCol = Math.min(minCol, col);
            maxCol = Math.max(maxCol, col);

            // 左子节点：列索引-1，更新minCol
            if (node.left != null) {
                queue.offer(new Pair<>(node.left, col - 1));
                minCol = Math.min(minCol, col - 1);
            }
            // 右子节点：列索引+1，更新maxCol
            if (node.right != null) {
                queue.offer(new Pair<>(node.right, col + 1));
                maxCol = Math.max(maxCol, col + 1);
            }
        }

        // 按列索引范围[minCol, maxCol]顺序输出
        for (int i = minCol; i <= maxCol; i++) {
            result.add(colMap.get(i));
        }
        return result;
    }

    // 辅助Pair类（若JDK<14可替换为AbstractMap.SimpleEntry）
    static class Pair<K, V> {
        K key;
        V value;
        Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }
        K getKey() { return key; }
        V getValue() { return value; }
    }
}

代码说明

1. 列索引动态更新：
   • 根节点初始列索引为 0，左子节点 -1，右子节点 +1。
   • minCol/maxCol 实时更新，避免最后对 HashMap 的 keySet 排序（节省 O(KlogK) 时间）。
2. BFS保证顺序：
   • 层序遍历确保同列节点按从上到下收集。
   • 同层节点按从左到右入队，保证同列同行的顺序。
3. 哈希表操作优化：
   • computeIfAbsent 方法简化列表初始化。
4. Pair类替代：
   • 若使用 JDK <14，可用 AbstractMap.SimpleEntry 替代自定义 Pair 类。