题目大意：
重新规划路线
n 座城市，从 0 到 n-1 编号，其间共有 n-1 条路线。因此，要想在两座不同城市之间旅行只有唯一一条路线可供选择（路线网形成一颗树）。去年，交通运输部决定重新规划路线，以改变交通拥堵的状况。
路线用 connections 表示，其中 connections[i] = [a, b] 表示从城市 a 到 b 的一条有向路线。
今年，城市 0 将会举办一场大型比赛，很多游客都想前往城市 0 。
请你帮助重新规划路线方向，使每个城市都可以访问城市 0 。返回需要变更方向的最小路线数。
题目数据 保证 每个城市在重新规划路线方向后都能到达城市 0 。
示例 1：
输入：n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]] 输出：3 解释：更改以红色显示的路线的方向，使每个城市都可以到达城市 0 。
示例 2：
输入：n = 5, connections = [[1,0],[1,2],[3,2],[3,4]] 输出：2 解释：更改以红色显示的路线的方向，使每个城市都可以到达城市 0 。
示例 3：
输入：n = 3, connections = [[1,0],[2,0]] 输出：0
提示：
- 2 <= n <= 5 * 10^4
- connections.length == n-1
- connections[i].length == 2
- 0 <= connections[i][0], connections[i][1] <= n-1
- connections[i][0] != connections[i][1]
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1466
解题思路分析：
题目描述中很明确的表示出这是一道树型结构问题，对于任意的树形结构，实际上都可以理解为一个有向图，所有路径的方向都是从根节点指向叶子节点。而本题有些特殊，路径的方向是叶子节点指向根节点，但这并不影响解题，因为在树形结构中，从任意一个节点到达根节点的路径都是有且只有一条，反过来，从根节点到任意一个节点的路径也是具有唯一性。因此本题我们同样可以从根节点向每一个叶子节点的方向进行dfs遍历。
解题时，我们首先需要构建出树形结构，利用题目给出的connections路径数组，找出每一个点能够直接连接到的其他点的集合。由于本题的特殊性，这里需要注意一点，在保存其他临节点集合时，除了需要记录临节点编号之外，我们还需要记录下当前点到临节点间路径的方向，比如1代表路径方向为当前节点到临节点，2代表临节点到当前节点。
构建好树形结构后，我们从根节点开始进行熟悉的dfs遍历操作。在每一层的dfs递归中，首先从树形结构中找出当前节点的所有临节点集合，查看当前节点与其组成路径的方向，如果方向为1（当前节点指向临节点），说明不符合题意，这是一条需要重新规划的路线，因此返回结果加一。反之，代表当前路径已经符合要求。dfs完所有节点后，也就能够统计出所有不符合题意的节点个数。另外解题时还要注意一下dfs的方向，如果临节点集合中存在当前节点的父节点，则跳过该节点，避免逆向遍历。
实现代码：
public int minReorder(int n, int[][] connections) {
List<int[]>[] map=new ArrayList[n]; // 记录每个节点的临节点
for(int[] c : connections){ // 遍历每一条路径
// 路径起点与终点
int from=c[0],to=c[1];
// 找到起点的临节点集合
if(map[from]==null)map[from]=new ArrayList<>();
// 将终点加入到起点的临节点集合，并设置路径方向为1
map[from].add(new int[]{to,1});
// 找到终点的临节点集合
if(map[to]==null)map[to]=new ArrayList<>();
// 将起点加入到终点的临节点集合，并设置路径方向为2
map[to].add(new int[]{from,2});
}
return dfs(map,0,0); // dfs求解
}
// map：树形结构
// node：当前节点
// parent：当前节点的父节点
// 返回结果：当前节点下需要修改的路径数
int dfs(List<int[]>[] map, int node, int parent){
// 当前节点的临节点集合
List<int[]> list=map[node];
int res=0; // 返回结果
for(int[] city : list){ // 循环每一个临节点
// 如果临节点是父节点，跳过（不走回头路）
if(city[0]==parent) continue;
// 如果到临节点的路径为顺方向，返回结果加一
// 顺方向代表从根节点到叶子节点方向，与题目要求相反
if(city[1]==1) res++;
// dfs到临节点，并累加子问题结果
res+=dfs(map,city[0],node);
}
return res;
}本题解法执行时间为33ms。
Runtime: 33 ms, faster than 83.01% of Java online submissions for Reorder Routes to Make All Paths Lead to the City Zero.
Memory Usage: 60.7 MB, less than 100.00% of Java online submissions for Reorder Routes to Make All Paths Lead to the City Zero.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1466-reorder-routes-to-make-all-paths-lead-to-the-city-zero-解题思路分析/