LeetCode课程表II：反转DFS后序遍历为何会出错？

核心原因是你代码里建的是反向依赖图，和拓扑排序常用的图结构完全反过来了，导致后序遍历的结果本身就是合法的拓扑顺序，根本不需要反转。

1. 常规拓扑图 vs 你的反向图 #

拓扑排序正常的做法是：

• 建「先修课 → 后续课」的有向图：比如prerequisites = [[1,0]]表示1得先学0，那图里就有一条0→1的边，意思是学完0才能学1。
• 这种图跑DFS后序遍历，会先把所有后续课处理完再加入先修课，后序结果是[1,0]，反转之后才是[0,1]，符合先学0再学1的顺序。

但你代码里的操作刚好相反：

• 碰到[[1,0]]，你把pre[0]（也就是课程1）当键，把pre[1]（课程0）加到它的邻接表里，等于建了一条1→0的边，意思是1依赖0——这是**「后续课 → 先修课」的反向图**。

2. 你的反向图跑后序遍历的逻辑 #

拿测试用例1举例：

• 遍历到课程1时，先递归访问它的先修课0；
• 0没有任何依赖，直接被加到postOrder里；
• 回到课程1，处理完所有依赖后也加到postOrder；
• 最后处理没依赖的课程2，也加进去。
• 最终postOrder是[0,1,2]，这本身就是合法的拓扑顺序（先学0，再学1，2随便什么时候学都行）。

这时候你要是反转，得到[2,1,0]，明显违反了1需要先学0的规则，肯定过不了测试。

3. 代码里的小优化点 #

你的图构建还有个小问题：没依赖的课程（比如测试用例1里的2）不会被加到graph的键里，虽然DFS里判断了graph.get(v) != null不会报错，但可以提前初始化所有课程的邻接表，省掉null判断：

// 先给所有课程初始化空的邻接表
for (int i = 0; i < numCourses; i++) {
    graph.put(i, new ArrayList<>());
}
// 再填充依赖关系
for (int[] pre : prerequisites) {
    graph.get(pre[0]).add(pre[1]);
}

总结 #

因为你把依赖边的方向搞反了，建了反向图，所以后序遍历的结果直接就是合法的拓扑排序，不需要反转。要是按常规思路建「先修→后续」的边，那才需要反转后序结果。

内容的提问来源于stack exchange，提问作者Lola