資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中樹的距離之和
假設我們有一個無向連通樹，其中存在 N 個節點。這些節點標記為 0...N-1，並且給出 N-1 條邊。第 i 條邊連線節點 edges[i][0] 和 edges[i][1]。我們必須找到一個列表，其中 ans[i] 是節點 i 與所有其他節點之間距離的總和。
因此，如果輸入類似於 N = 6 且 edges = [(0,1),(0,2),(2,3),(2,4),(2,5)]，則輸出將為 [8,12,6,10,10,10]
為了解決這個問題，我們將遵循以下步驟：
定義一個函式 dfs1()，它將接收節點、父節點作為引數。
對於初始化 i := 0，當 i < graph[node] 的大小，更新（i 增加 1），執行：
child := graph[node, i]
如果 child 不等於 parent，則：
dfs1(child, node)
cnt[node] := cnt[node] + cnt[child]
ans[node] := ans[node] + cnt[child] + ans[child]
定義一個函式 dfs2()，它將接收節點、父節點作為引數。
對於初始化 i := 0，當 i < graph[node] 的大小，更新（i 增加 1），執行：
child := graph[node, i]
如果 child 不等於 parent，則：
ans[child] := ans[node] - cnt[child] + N - cnt[child]
dfs2(child, node)
定義一個數組 ans
定義一個數組 cnt
定義一個具有 10005 行的陣列 graph
從主方法中，執行以下操作：
N of this := N
ans := 定義一個大小為 N 的陣列
cnt := 定義一個大小為 N 的陣列，並用 1 填充它
n := edges 的大小
對於初始化 i := 0，當 i < n，更新（i 增加 1），執行：
u := edges[i, 0]
v := edges[i, 1]
在 graph[u] 的末尾插入 v
在 graph[v] 的末尾插入 u
dfs1(0, -1)
dfs2(0, -1)
返回 ans
讓我們看看以下實現以獲得更好的理解：
示例
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0;
i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
void dfs1(int node, int parent) {
for (int i = 0; i < graph[node].size(); i++) {
int child = graph[node][i];
if (child != parent) {
dfs1(child, node);
cnt[node] += cnt[child];
ans[node] += cnt[child] + ans[child];
}
}
}
void dfs2(int node, int parent) {
for (int i = 0; i < graph[node].size(); i++) {
int child = graph[node][i];
if (child != parent) {
ans[child] = ans[node] - cnt[child] + N - cnt[child];
dfs2(child, node);
}
}
}
vector<int> ans;
vector<int> cnt;
vector<int> graph[10005];
int N;
vector<int> sumOfDistancesInTree(int N, vector<vector<int> >& edges) {
this->N = N;
ans = vector<int>(N);
cnt = vector<int>(N, 1);
int n = edges.size();
for (int i = 0; i < n; i++) {
int u = edges[i][0];
int v = edges[i][1];
graph[u].push_back(v);
graph[v].push_back(u);
}
dfs1(0, -1);
dfs2(0, -1);
return ans;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{0,1},{0,2},{2,3},{2,4},{2,5}}; print_vector(ob.sumOfDistancesInTree(6, v));
}輸入
{{0,1},{0,2},{2,3},{2,4},{2,5}}輸出
[8, 12, 6, 10, 10, 10, ]
637 次檢視
