看了这个题解看懂了https://leetcode-cn.com/problems/sum-of-distances-in-tree/solution/c-liang-ci-dfsde-dao-da-an-by-congwang357-2/
核心就在这里：
※求出递推式；
※先使用后序遍历求出ans[root]和所有cnt[i]，然后使用前序遍历用ans[node]求出ans[node的孩子]；
※使用用数组存储邻接点的方式存储图。
class Solution { public: vector<vector<int>> g; //存储图 vector<int> ans,cnt; int n; //方便函数调用N vector<int> sumOfDistancesInTree(int N, vector<vector<int>>& edges) { if(N==0||edges.empty()) return {0}; ans.resize(N); //ans[i]初值为0 cnt.resize(N); //cnt[i]初值为1 cnt.assign(N,1); g.resize(N); n=N; int i,j,k,e=edges.size(); for(i=0;i<e;++i){ //从edges读入g（图） g[edges[i][0]].push_back(edges[i][1]); g[edges[i][1]].push_back(edges[i][0]); //把邻接点存储到节点中，这样不用花费二维数组（邻接矩阵），相当于邻接表 } dfs1(0,-1); //得到ans[root]和所有cnt[i] dfs2(0,-1); //利用ans[root]和cnt[i]递归求出ans[i] return ans; } void dfs1(int node,int parent){ //后序遍历 for(int i=0;i<g[node].size();++i){ //遍历所有儿子 if(g[node][i]==parent) continue; //跳过父结点 dfs1(g[node][i],node); //递归计算ans和cnt（会从最底层的叶子开始往上返回） cnt[node]+=cnt[g[node][i]]; ans[node]+=ans[g[node][i]]+cnt[g[node][i]]; } } void dfs2(int node,int parent){ //前序遍历 for(int i=0;i<g[node].size();++i){ if(g[node][i]==parent) continue; ans[g[node][i]]=ans[node]+n-2*cnt[g[node][i]]; //计算ans[node]，然后利用ans[node]往下计算ans[node的儿子] dfs2(g[node][i],node); } } };
