Leetcode 2477. 到达首都的最少油耗（建图 + DFS 一次遍历）

本文主要是介绍Leetcode 2477. 到达首都的最少油耗（建图 + DFS 一次遍历），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Leetcode 2477. 到达首都的最少油耗（建图 + DFS 一次遍历）
题目
- 给你一棵 n 个节点的树（一个无向、连通、无环图），每个节点表示一个城市，编号从 0 到 n - 1 ，且恰好有 n - 1 条路。0 是首都。给你一个二维整数数组 roads ，其中 roads[i] = [ai, bi] ，表示城市 ai 和 bi 之间有一条双向路。
- 每个城市里有一个代表，他们都要去首都参加一个会议。
- 每座城市里有一辆车。给你一个整数 seats 表示每辆车里面座位的数目。
- 城市里的代表可以选择乘坐所在城市的车，或者乘坐其他城市的车。相邻城市之间一辆车的油耗是一升汽油。
- 请你返回到达首都最少需要多少升汽油。
- 1 <= n <= 10 ^ 5
- roads.length == n - 1
- roads[i].length == 2
- 0 <= ai, bi < n
- ai != bi
- roads 表示一棵合法的树。
- 1 <= seats <= 10 ^ 5
解法
- 建图 + DFS 一次遍历：
- 第 1 步：
- 思考不走回头路肯定是最优的，因此每个叶子节点均会发车
- 第 2 步：
- 如果车上座位比较多，则发车到父节点后，将所有人塞入最少的车
- 第 3 步：
- 实现仅在回溯时处理，
  - 叶子节点发一辆车，载一个人
  - 非叶子节点、将所有孩子节点的人加自己塞入最少的车
  - 根节点不能再发车了
- 第 4 步：
- 具体实现可以仅回溯人数 human，使用（human+seats-1）/seats 确定最少发了几辆车
- 注意：发车到根节点即可，根节点不发车
- 时间复杂度：O（n），空间复杂度：O（n+height）建树+递归栈深度
代码

/*** 建图 + DFS 一次遍历：** 第 1 步：* 思考不走回头路肯定是最优的，因此每个叶子节点均会发车** 第 2 步：* 如果车上座位比较多，则发车到父节点后，将所有人塞入最少的车** 第 3 步：* 实现仅在回溯时处理，*     * 叶子节点发一辆车，载一个人*     * 非叶子节点、将所有孩子节点的人加自己塞入最少的车*     * 根节点不能再发车了** 第 4 步：* 具体实现可以仅回溯人数 human，使用（human+seats-1）/seats 确定最少发了几辆车* 注意：发车到根节点即可，根节点不发车* 时间复杂度：O（n），空间复杂度：O（n+height）建树+递归栈深度**/private long res;public long minimumFuelCost(int[][] roads, int seats) {this.res = 0L;int n = roads.length + 1;// 建树List<Integer>[] edgeList = buildTree(n, roads);// 递归遍历树dfsTraversalTree(0, -1, edgeList, seats);return this.res;}private List<Integer>[] buildTree(int n, int[][] edges) {List<Integer>[] edgeList = new ArrayList[n];for (int i = 0; i < n; i++) {edgeList[i] = new ArrayList<>();}for (int i = 0; i < edges.length; i++) {int u = edges[i][0];int v = edges[i][1];edgeList[u].add(v);edgeList[v].add(u);}return edgeList;}private int dfsTraversalTree(int son, int father, List<Integer>[] edgeList, int seats) {int human = 1;// 叶子节点if (edgeList[son].size() == 1 && edgeList[son].get(0).equals(father)) {// 到父节点发一辆车消耗一升油this.res++;return human;}for (int next : edgeList[son]) {if (next != father) {human += dfsTraversalTree(next, son, edgeList, seats);}}// 发车到根节点即可，根节点不发车if (son != 0) {// 到父节点多少辆车就是会消耗多少升油this.res += (human + seats - 1) / seats;}return human;}