題目描述:
給定一棵 n 個節點的樹,根節點為 0(首都)。每個非根節點恰有一位代表。每個城市有一輛車,最多坐 seats 人。每條邊消耗 1 單位燃料。所有代表需要抵達首都。求最少的總燃料消耗。
解題思路: 使用 DFS 自底向上計算:
people。ceil(people / seats)。時間複雜度:O(n) — DFS 遍歷每個節點一次。
空間複雜度:O(n) — 鄰接表和遞迴堆疊深度。
1. Build adjacency list from roads
2. Define dfs(node, parent) -> number of people in subtree:
a. people = 1 (current node's representative)
b. For each child of node (not parent):
- people += dfs(child, node)
c. If node != 0 (not root):
- totalFuel += ceil(people / seats)
d. Return people
3. Call dfs(0, -1)
4. Return totalFuelBFS 拓撲排序 O(n):從葉節點開始 BFS,逐層向根聚合人數和燃料。用入度陣列驅動拓撲排序。避免遞迴深度問題但程式碼略長。
迭代 DFS O(n):用顯式堆疊模擬 DFS,適合避免遞迴堆疊溢出的場景。