https://leetcode.com/problems/sum-of-distances-in-tree/description/
首先想到的用brute force去解这道题:
对于每个节点，我们用BFS就可以求出每个level的点到该节点的距离，边遍历边求和。但是我们要对每个节点都要做一次BFS，时间复杂度为O(n*n)
仔细分析，其实有非常多的重复计算，那么去重就是这道题的分析关键。
那么重复到底在哪里？拿题目中给出的例子来说：
在计算其他节点到N0(node0, 节点0)的距离和的时候：(第一次遍历)
distance(1,2) -> 0 = 1，distance(3,4,5) -> 0 = 2，假设3往下还有(6,7)两个节点，distance(6,7) -> 0 = 3
接下来我们计算其他节点到N2的距离和的时候：(第二次遍历)
distance(3,4,5) -> 2 = 1, distance(6,7) -> 2 = 2
可以看到，在第一次遍历，已经计算，并且知道N2下面有3个点(3,4,5),和两个二重degree(6,7), 第二次遍历，竟然又一次计算N2下面有多少个点，每个点到它的距离是多少，这就是重复的地方。
那么如何去重？这部分是最难想的
在第二次遍历的时候，可以发现，所有N2已经N2往下的节点都靠近了，而除此之外的节点都远离了，所以只要知道N2和N2往下的节点总共有多少个，并且存下来count(2), count(2)个数的节点，距离都要减1，n – count(2)个数的节点，距离都要增加1，最后可以得到公式：
res(2) = res(0) – count(2) + (n – count(2))
所以在第一次遍历的时候，要记录res(0), 和count(i), i from 0 to n – 1，通过这些信息，在第二次遍历的时候，通过刚才的公式，可以得到所有点的结果。
基本功：
1. 二维array转换成无向图，数据结构的选择为Set<Integer>[]
2. 树的后序遍历
3. BFS
Matthew Xie 