LeetCode 987. 二叉树的垂序遍历

2025-04-03 HGNULB 约 11 分钟

文章信息 7 个分类 6 个标签

分类

题目描述

✅ 987. 二叉树的垂序遍历

题意分析

给二叉树的每个节点安一个坐标：根是 (row = 0, col = 0)，左孩子是 (row + 1, col - 1)，右孩子是 (row + 1, col + 1)。要求把节点按「列」分组，列号从小到大输出；同一列内行号从小到大；如果同一个 (row, col) 位置上挤了多个节点（不同分支完全可能撞到同一格），这些节点按值从小到大排列。返回一个二维列表，每个子列表是一列。

三条排序规则是层层兜底的关系：先比列，列相同比行，行也相同比值。这正是三元组 (col, row, val) 的字典序——三条规则可以合并成一条。认出这一点，题目就从「困难」塌回「中等」。

最容易被忽略的是第三条。它是本题与 314 题最本质的差别：314 只要求同列内自上而下，同一格的节点保持遍历顺序即可；987 明确要求按值排序，而任何遍历顺序都不能保证同一格的节点恰好按值到达。这条规则决定了不能靠「精心安排遍历顺序」蒙混过关，必须显式排序。

约束里节点数不超过 1000、节点值在 0 到 1000 之间，规模极小，$O(n \log n)$ 绰绰有余，说明考点是规则的正确表达而不是效率。

边界：列号会是负数（一路向左时 col 递减），所以不能拿它直接当数组下标；树至少有 1 个节点，但子节点随时可能为空；最左列和最右列都要出现在答案里，中间不会有空列（因为从根到任意节点的路径上列号每次只变化 1，列号集合必然连续）。

解法：坐标采集后排序分组

核心思路

最自然的写法是开一个 col → 节点值列表 的哈希表，遍历时把 node.val 追加到对应列，最后按列号排序输出。这个写法能过 314 题，但在 987 上是错的：追加顺序就是遍历顺序，而遍历顺序与题目要求的顺序无关。DFS 会把整条左子树先走完，同一列里 row = 2 的节点可能排在 row = 1 的前面；换成 BFS 能修好行序，却修不好第三条——同一格的多个节点按入队先后排列，跟值的大小毫无关系。

瓶颈就在这里：输出顺序是三条规则共同决定的，而遍历只能提供其中一维的天然有序性。与其绞尽脑汁设计一种同时满足三条的遍历，不如干脆承认遍历只负责「采集」，顺序交给排序。

关键观察：把每个节点表示成三元组 (col, row, val) 之后，题目要求的全序恰好就是这个三元组的字典序。于是遍历的任务被彻底简化成——访问每个非空节点，记录它的三元组，用 DFS 还是 BFS、先序还是后序，全都无所谓，因为坐标是随参数传下去的，与访问次序无关。

采集完成后对整个数组按字典序排一次。此时的不变量是：排序后的序列中，列号相同的元素必定连续出现，且这一段内部先按 row 升序、row 相同再按 val 升序。「连续出现」由字典序的第一关键字保证，「段内有序」由第二、三关键字保证——这两点合起来意味着答案已经排好了，只差把它切开。

切分因此只需一次线性扫描：记住上一个元素的列号，遇到列号变化就新开一个子列表，否则追加到当前子列表。不需要哈希表，也不需要对列号再排序一次，因为它们本来就是升序出现的。

这里有个容易被忽略的细节：切分需要一个「当前还没有任何列」的标记。列号 0 是完全合法的取值（根节点就在第 0 列），所以不能用 prevCol = 0 当哨兵去判断「是不是第一个元素」，必须另设一个布尔量 hasCol。

解题步骤

DFS 采集坐标：从 (row = 0, col = 0) 开始递归，节点为空立即返回。空判放在函数入口而不是调用前，可以让左右孩子的递归写成无条件的两行，代码更短也更不容易漏分支。

入表：对每个非空节点存三元组 (col, row, val)。元组里 col 必须排在 row 前面——后面直接按下标 0、1、2 比较，字段顺序就是排序优先级，摆错顺序就变成了按行分组的层序遍历。

向下传坐标：左孩子 (row + 1, col - 1)，右孩子 (row + 1, col + 1)。row 两边都加 1，col 一减一加，这是坐标系的定义，记反就左右镜像。

三关键字排序：先比 col，相等再比 row，再相等比 val。三档一个都不能少：漏掉最后一档时，Java 的 List.sort 是稳定排序，结果会静默退化成遍历顺序；Go 的 sort.Slice 不保证稳定，同一份输入甚至可能给出不同结果。

线性切分：顺序扫描排序结果，用 hasCol 和 prevCol 判断是否需要新开一列，然后把 val 追加进最后一个子列表。

返回结果。

以官方样例 root = [1,2,3,4,6,5,7] 走一遍。这棵树的结构是：根 1；1 的左孩子 2、右孩子 3；2 的左孩子 4、右孩子 6；3 的左孩子 5、右孩子 7。

DFS 按先序采集，得到的原始顺序是：
访问 1，坐标 (row 0, col 0)，记 (0, 0, 1)；
进左子树访问 2，(row 1, col -1)，记 (-1, 1, 2)；
访问 4，(row 2, col -2)，记 (-2, 2, 4)；
访问 6，(row 2, col 0)，记 (0, 2, 6)；
回到根进右子树访问 3，(row 1, col 1)，记 (1, 1, 3)；
访问 5，(row 2, col 0)，记 (0, 2, 5)；
访问 7，(row 2, col 2)，记 (2, 2, 7)。

注意原始序列里 (0, 2, 6) 排在 (0, 2, 5) 前面——6 和 5 撞在了同一格 (row 2, col 0)，而 DFS 先走左子树，所以 6 先到。这就是「遍历顺序不可信」的现场证据。

排序后：(-2,2,4)、(-1,1,2)、(0,0,1)、(0,2,5)、(0,2,6)、(1,1,3)、(2,2,7)。第三关键字在此生效，5 被换到了 6 前面。

线性切分：第一个元素 col = -2，hasCol 为假，新开一列得 [[4]]，prevCol = -2；下一个 col = -1 与 prevCol 不同，新开得 [[4],[2]]；下一个 col = 0 不同，新开得 [[4],[2],[1]]；接着 (0,2,5) 与 prevCol = 0 相同，追加得 [...,[1,5]]；(0,2,6) 仍相同，追加得 [1,5,6]；col = 1 新开；col = 2 新开。

最终返回 [[4],[2],[1,5,6],[3],[7]]。如果沿用「边遍历边追加」的写法，第 2 列会是 [1,6,5]，与期望差一个位置。

代码实现

class Solution {
    // DFS 或 BFS 都可以采集坐标，根节点为 (row=0, col=0)，左孩子行加一列减一，右孩子行加一列加一。
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<int[]> nodes = new ArrayList<>();
        dfs(root, 0, 0, nodes);

        nodes.sort((a, b) -> {
            if (a[0] != b[0]) {
                return Integer.compare(a[0], b[0]);
            }
            if (a[1] != b[1]) {
                return Integer.compare(a[1], b[1]);
            }
            return Integer.compare(a[2], b[2]);
        });

        List<List<Integer>> res = new ArrayList<>();
        int prevCol = 0;
        boolean hasCol = false;
        for (int[] node : nodes) {
            if (!hasCol || node[0] != prevCol) {
                res.add(new ArrayList<>());
                hasCol = true;
                prevCol = node[0];
            }

            res.get(res.size() - 1).add(node[2]);
        }

        return res;
    }

    private 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);
    }
}

func verticalTraversal(root *TreeNode) [][]int {
    // DFS 或 BFS 都可以采集坐标，根节点为 (row=0, col=0)，左孩子行加一列减一，右孩子行加一列加一。
    type item struct {
        col int
        row int
        val int
    }

    items := make([]item, 0)

    var dfs func(node *TreeNode, row, col int)
    dfs = func(node *TreeNode, row, col int) {
        if node == nil {
            return
        }

        items = append(items, item{col: col, row: row, val: node.Val})

        dfs(node.Left, row+1, col-1)
        dfs(node.Right, row+1, col+1)
    }

    dfs(root, 0, 0)

    sort.Slice(items, func(i, j int) bool {
        if items[i].col != items[j].col {
            return items[i].col < items[j].col
        }
        if items[i].row != items[j].row {
            return items[i].row < items[j].row
        }
        return items[i].val < items[j].val
    })

    res := make([][]int, 0)
    prevCol := 0
    hasCol := false
    for _, it := range items {
        if !hasCol || it.col != prevCol {
            res = append(res, []int{})
            hasCol = true
            prevCol = it.col
        }

        res[len(res)-1] = append(res[len(res)-1], it.val)
    }

    return res
}

复杂度分析

时间复杂度：$O(n \log n)$，其中 $n$ 为节点数。DFS 采集每个节点一次是 $O(n)$，切分再扫一遍也是 $O(n)$，全部代价压在中间那次三关键字排序上。凭的是「排序后同列元素必然连续」这个性质——正因为有它，分组阶段才不需要哈希表，也不需要对列号二次排序。

空间复杂度：$O(n)$，三元组数组存了全部 $n$ 个节点，是主要开销；递归栈深度等于树高，最坏（退化成链）也是 $O(n)$，与前者同阶；输出本身同样是 $O(n)$。凭的是本解法「先全量落地再统一处理」的策略，用一份线性缓冲换掉了在遍历过程中维护多层有序结构的复杂度。

关键点总结

多级排序规则（主关键字、次关键字、末关键字）能直接合并成元组的字典序，一次排序解决全部规则。这是最值得迁移的一条：凡是「先按 A、A 相同按 B、B 相同按 C」的题面，先想元组排序。

遍历只负责采集，不负责定序。坐标是通过递归参数传下去的，与访问次序解耦，所以 DFS 和 BFS 完全等价——想清楚这一点能省掉大量「该用哪种遍历」的纠结。

元组的字段顺序就是排序优先级。把 col 写在 row 前面是有意为之，不是随手排的。

排序后同一列连续出现，因此分组是一次线性扫描而非哈希表 + 二次排序。数据「已经有序」时要意识到后续处理可以降级。

列号取负值是常态，所以不能拿它当数组下标；要么排序，要么先求出最小列号做偏移。

面试视角：面试官考这题的核心意图，是看你会不会掉进「用遍历顺序代替排序」的坑。上来就要主动点明第三条规则（同一格按值排序）以及它与 314 题的区别，然后给出三元组方案。被追问「能不能不用全局排序」时，标准答复是用 TreeMap<col, TreeMap<row, PriorityQueue<val>>> 这类嵌套有序结构，复杂度同阶但常数更大、手写更易错，白板上不推荐。

易错点总结

边遍历边把值追加进 col → list 哈希表：[1,2,3,4,6,5,7] 中 6 和 5 都落在 (row 2, col 0)，DFS 先走左子树所以 6 先入表，第 0 列得到 [1,6,5]，期望是 [1,5,6]。

改用 BFS 就以为万事大吉：BFS 确实保证了行号递增，但第 2 层的入队顺序是 4、6、5、7，同一格的 6 仍然排在 5 前面，第 0 列还是 [1,6,5]。行序对了，值序仍错。

比较器漏掉第三档 val：Java 的 List.sort 稳定，静默退化成遍历顺序，[1,2,3,4,6,5,7] 输出 [1,6,5]；Go 的 sort.Slice 不保证稳定，同一份输入换个运行环境可能给出 [1,5,6]，本地对了线上挂，是最难排查的一类。

三元组存成 (row, col, val) 却仍按下标 0、1、2 比较：主关键字变成行号，[1,2,3,4,6,5,7] 会被按层切分成 [[1],[2,3],[4,5,6,7]]，输出的是层序遍历而不是垂序遍历。

不设 hasCol 标志，用 prevCol = 0 当哨兵：单节点树 [1] 的唯一节点列号就是 0，与 prevCol 相等，于是不新建子列表，紧接着 res.get(res.size() - 1) 在空列表上取值，抛 IndexOutOfBoundsException。这个坑只在最小列号恰好为 0 时爆炸，随机样例经常测不出来。

左右孩子的列号加减写反（左 col + 1、右 col - 1）：[1,2,3,4,6,5,7] 输出变成左右镜像的 [[7],[3],[1,5,6],[2],[4]]，每一列内容对但整体倒序。

只更新 col 忘了 row + 1：所有节点行号都是 0，同列排序退化为按值排序。根为 5、右孩子为 2、2 的左孩子为 1 时，第 0 列的正确答案是 [5,1]（5 在第 0 行、1 在第 2 行），漏掉 row 会输出 [1,5]。

拿列号直接当数组下标：一路向左的链 1 → 2 → 3 中列号是 0、-1、-2，arr[-1] 立刻越界。要用数组必须先扫出最小列号做偏移。

用 PriorityQueue 存同格节点后直接 for-each 取值：Java 的 PriorityQueue 迭代器返回的是堆的内部数组顺序而非有序序列，第 0 列装入 1、6、5 后遍历可能得到 [1,6,5]，必须反复 poll() 才有序。

DFS 里在调用前判空、入口不判空：漏掉某个分支的判空时（比如只写了 if (node.left != null)），另一侧为空的叶子节点会直接空指针；把判空统一放在函数入口，两个递归调用就可以无条件写。

相似题目

题目	难度	考察点
314. 二叉树的垂直遍历	中等	同样的坐标体系，但同一格不要求按值排序，BFS 边遍历边追加即可，不需要全局排序
102. 二叉树的层序遍历	中等	按行分组而不是按列，行号天然随 BFS 递增，一层一层出队即可
103. 二叉树的锯齿形层序遍历	中等	在层序基础上按层号奇偶翻转方向，考的是输出阶段的方向控制
199. 二叉树的右视图	中等	只取每行的最后一个节点，是层序分组后的降维，不涉及列坐标
662. 二叉树最大宽度	中等	用完全二叉树编号（左 `2i`、右 `2i+1`）而非 ±1 列号，考的是编号溢出与同层首尾作差
429. N 叉树的层序遍历	中等	孩子数不再是 2，坐标类技巧失效，只能靠队列逐层展开
863. 二叉树中所有距离为 K 的结点	中等	先建父指针把树变成无向图再 BFS，考的是把树坐标问题转成图上的距离问题