题解 | #我们的距离#
我们的距离
http://www.nowcoder.com/practice/14de961632784129a17a512c4a214d4a
题意：
给定一棵树，遍历树的每一个节点，都返回一个值，这个值是该节点到其他节点的边长之和。
方法一：
暴力dfs（超时）
思路：直接模拟。从树的每个节点出发做 dfs ，记录该节点到其他节点的长度，并将长度累加。
class Solution {
public:
vector<long> solve(int n, vector<Point>& edge) {
vector<vector<int>> g(n+1);//建树
vector<int> dis(n+1);//某节点到其他节点的长度
vector<long> res;
for(int i=0;i<n-1;i++){
int x=edge[i].x,y=edge[i].y;
g[x].push_back(y);//无向
g[y].push_back(x);
}
for(int i=1;i<=n;i++){//遍历每个节点
long sum=0;
dfs(i,i,g,dis);//对每个节点都dfs
for(int j=1;j<=n;j++){//返回某节点到其他节点的权值之和
sum+=dis[j];
dis[j]=0;
}
res.push_back(sum);
}
return res;
}
void dfs(int x,int fa,vector<vector<int>> g,vector<int>& dis){
int num=g[x].size();
for(int i=0;i<num;i++){//遍历节点x 的全部边
int y=g[x][i];
if(y!=fa){//未访问过，则访问
dis[y]=dis[x]+1;
dfs(y,x,g,dis);
}
}
}
}; 时间复杂度：%2Cn%E6%98%AF%E8%8A%82%E7%82%B9%E6%95%B0%E9%87%8F%EF%BC%8C%E5%A4%96%E5%B1%82%E5%BE%AA%E7%8E%AF%E9%81%8D%E5%8E%86%E6%AF%8F%E4%B8%AA%E8%8A%82%E7%82%B9%EF%BC%8C%E5%86%85%E5%B1%82dfs%E4%B9%9F%E6%98%AF%E9%81%8D%E5%8E%86%E6%AF%8F%E4%B8%AA%E8%8A%82%E7%82%B9%E3%80%82)
空间复杂度：%2Cn%20%E6%98%AF%E6%A0%91%E7%9A%84%E8%8A%82%E7%82%B9%E4%B8%AA%E6%95%B0%EF%BC%8C%E9%82%BB%E6%8E%A5%E8%A1%A8%E5%AD%98%E5%82%A8%E6%A0%91%E8%8A%82%E7%82%B9%E7%9A%84%E8%BE%B9%E9%9B%86%E3%80%82)
方法二：
两次dfs
思路：第一次 dfs 计算每个节点作为根节点构成的子树中节点的数量 和 计算一号节点到其他节点的权值之和；
第二次 dfs 计算每个节点到其他节点的边长之和。
例子如下：
class Solution {
public:
vector<long> solve(int n, vector<Point>& edge) {
vector<vector<int>> g(n+1);//建树
vector<int> sum(n+1);//存储每个节点作为根节点构成的子树中节点的数量
vector<long> res(n+1);
for(int i=0;i<n-1;i++){
int x=edge[i].x,y=edge[i].y;
g[x].push_back(y);//无向
g[y].push_back(x);
}
dfs1(1,1,g,sum,res,0);
dfs2(1,1,g,sum,res,n);
res.erase(res.begin());//下标从1开始
return res;
}
void dfs1(int x,int fa,vector<vector<int>> g,vector<int>& sum,vector<long>& res,int dep){
int num=g[x].size();
sum[x]=1;
for(int i=0;i<num;i++){//遍历节点x的全部边
int y=g[x][i];
if(y!=fa){//未访问过，则访问
dfs1(y,x,g,sum,res,dep+1);
sum[x]+=sum[y];
}
}
res[1]+=dep;
}
void dfs2(int x,int fa,vector<vector<int>> g,vector<int>& sum,vector<long>& res,int n){
int num=g[x].size();
for(int i=0;i<num;i++){//遍历节点x的全部边
int y=g[x][i];
if(y!=fa){//未访问过，则访问
res[y]=res[x]-sum[y]+n-sum[y];
dfs2(y,x,g,sum,res,n);
}
}
}
};
时间复杂度：%2Cn%E6%98%AF%E8%8A%82%E7%82%B9%E6%95%B0%E9%87%8F%EF%BC%8C%E4%B8%A4%E6%AC%A1dfs%2C%E6%AF%8F%E6%AC%A1dfs%E9%81%8D%E5%8E%86%E6%AF%8F%E4%B8%AA%E8%8A%82%E7%82%B9%E3%80%82)
空间复杂度：
投递美团等公司7个岗位
