## Monday, August 8, 2016

### Google – Average Length of City Path

Google – Average Length of City Path

[Solution]

(1)算degree
(2)逐层删leaf node来找root。就是Minimum Height Tree的算法。
(3)在删leaf node的过程中多做两件事：建tree和计算sub tree size(包括该节点本身)。如果在第(2)步有两个root，随便选一个作为root，另一个作为子节点就好。这里的主要目的是建Tree.
(4)如果总共有N个结点，当前结点v的sub tree size为K (包括v本身)，那么连接v和其parent的那条edge就会被遍历K * (N-K)次。

(5)构建完tree，证明完(4)，剩下的只需要对tree做一个dfs traversal，就可以得到总的path sum。再除以n-1就可以得到答案了。
`class` `Solution2 {`
`  ``int` `sum = ``0``;`
`  ``int` `n;`
`  ``public` `int` `averagePathLength(``int` `n, ``int``[][] graph) {`
`    ``if` `(n <= ``1``) {`
`      ``return` `0``;`
`    ``}`
`    `
`    ``this``.n = n;`
`    `
`    ``// get degree of every node`
`    ``Map<Integer, Integer> degree = ``new` `HashMap<>();`
`    ``for` `(``int` `i = ``0``; i < n; i++) {`
`      ``for` `(``int` `j = ``0``; j < n; j++) {`
`        ``if` `(graph[i][j] != ``0``) {`
`          ``degree.put(i, degree.getOrDefault(i, ``0``) + ``1``);`
`          ``degree.put(j, degree.getOrDefault(j, ``0``) + ``1``);`
`        ``}`
`      ``}`
`    ``}`
`    `
`    ``// Build the tree`
`    ``TNode root = buildTree(degree, graph);`
`    `
`    ``// dfs traversal to get the path sum`
`    ``dfs(root);`
`    `
`    ``return` `sum / (n - ``1``);`
`  ``}`
`  `
`  ``private` `void` `dfs(TNode root) {`
`    ``if` `(root == ``null``) {`
`      ``return` `null``;`
`    ``}`
`    `
`    ``for` `(TNode child : root.children) {`
`      ``sum += child.size * (n - child.size) * graph[root.val][child.val];`
`      ``dfs(child);`
`    ``}`
`  ``}`
`  `
`  ``private` `TNode buildTree(Map<Integer, Integer> degree, ``int``[][] graph) {`
`    `
`    ``Map<Integer, TNode> nodeMap = ``new` `HashMap<>();`
`    ``for` `(``int` `i = ``0``; i < n; i++) {`
`      ``nodeMap.put(i, ``new` `TNode(i));`
`    ``}`
`    `
`    ``Queue<Integer> queue = ``new` `LinkedList<>();`
`    ``for` `(``int` `v : degree) {`
`      ``if` `(degree.get(v) == ``1``) {`
`        ``queue.add(v);`
`        ``nodeMap.get(v).size += ``1``;`
`      ``}`
`    ``}`
`    ``for` `(``int` `v : queue) {`
`      ``degree.remove(v);`
`    ``}`
`    `
`    ``while` `(``true``) {`
`      ``int` `size = queue.size();`
`      ``for` `(``int` `i = ``0``; i < size; i++) {`
`        ``int` `curr = queue.poll();`
`        ``int` `currSize = nodeMap.get(curr).size;`
`        `
`        ``for` `(``int` `adj = ``0``; adj < n; adj++) {`
`          ``if` `(graph[curr][adj] != ``0``) {`
`            ``nodeMap.get(adj).children.add(curr);`
`            ``nodeMap.get(adj).size += currSize;`
`            `
`            ``degree.put(adj, degree.get(adj) - ``1``);`
`            ``if` `(degree.get(adj) == ``1``) {`
`              ``queue.offer(adj);`
`            ``}`
`          ``}`
`        ``}`
`      ``}`
`      `
`      ``for` `(``int` `v : queue) {`
`        ``degree.remove(v);`
`      ``}`
`      `
`      ``if` `(degree.isEmpty()) {`
`        ``break``;`
`      ``}`
`    ``}`
`    `
`    `
`    ``if` `(queue.size() > ``1``) {`
`      ``int` `root1 = queue.poll();`
`      ``int` `root2 = queue.poll();`
`      ``nodeMap.get(root1).children.add(root2);`
`      ``nodeMap.get(root1).size += nodeMap.get(root2).size;`
`      ``return` `nodeMap.get(root1);`
`    ``}`
`    `
`    ``return` `nodeMap.get(queue.poll());`
`  ``}`
` `

`  ``private` `class` `TNode {`
`    ``int` `val;`
`    ``List<TNode> children;`
`    ``int` `size;`
`    `
`    ``TNode(``int` `val) {`
`      ``this``.val = val;`
`      ``this``.children = ``new` `ArrayList<>();`
`    ``}`
`  ``}`
`}`