## Sunday, April 10, 2016

### Sums of All Subtrees | tech::interview

Sums of All Subtrees | tech::interview

G家的新题。总的来说是一个bottom up的解法，先找出每一个level的所有节点，然后从最下面往上做level order traversal。

void all_sum(const unordered_map<int,int>& parents, const unordered_map<int,int>& values) {
int max_level = 0;
unordered_map<int,int> node_levels;
function<int(int)> calc_level = [&](int id) {
if(node_levels.count(id)) return node_levels[id];
int ret = (parents.at(id) == -1) ? 0 : calc_level(parents.at(id)) + 1;
max_level = std::max(max_level, ret);
node_levels[id] = ret;
return ret;
};

for(auto& p : parents) calc_level(p.first);
vector<vector<int>> levels(max_level + 1);
for(auto& p : node_levels) levels[p.second].push_back(p.first);

unordered_map<int,int> subtree_sums = values;

for(int i = (int)levels.size()-1; i >= 0; --i) {
for(auto& node : levels[i]) {
if(parents.at(node) != -1)
subtree_sums[parents.at(node)] += subtree_sums[node];
}
}
for(auto& p : subtree_sums)
cout << "Root: " << p.first << " Subtree sum: " << p.second << endl;
}

0(1)
/   \
1(2)  2(3)
/   \
3(4) 4(5)

all_sum({{0,-1},{1,0},{2,0},{3,1},{4,1}},
{{0,1},{1,2},{2,3},{3,4},{4,5}});

Root: 0 Subtree sum: 15
Root: 1 Subtree sum: 11
Root: 2 Subtree sum: 3
Root: 3 Subtree sum: 4
Root: 4 Subtree sum: 5
https://moonstonelin.wordpress.com/2016/04/09/sums-of-all-subtrees/
`public Dictionary<int, int> GetSum``3``(List<Node<int>> nodes)`
`{`
`    ``Dictionary<int, Node<int>> dict = new Dictionary<int, Node<int>>();`
`    ``Dictionary<int, int> result = new Dictionary<int, int>();`
`    ``HashSet<int> parentIds = new HashSet<int>();`
`    ``HashSet<int> leafIds = new HashSet<int>();`
`    ``Dictionary<int, List<int>> parentToChildrenIds = new Dictionary<int, List<int>>();`
`    ``int rootId = ``-1``;`

`    ``foreach (var n in nodes)`
`    ``{`
`        ``dict.Add(n.Id, n);`
`        ``parentIds.Add(n.ParentId);`

`        ``if (n.Id == n.ParentId)`
`        ``{`
`            ``rootId = n.Id;`
`        ``}`

`        ``if (!parentToChildrenIds.ContainsKey(n.ParentId))`
`        ``{`
`            ``parentToChildrenIds.Add(n.ParentId, new List<int>());`
`        ``}`

`        ``if (n.Id != n.ParentId)`
`        ``{`
`            ``parentToChildrenIds[n.ParentId].Add(n.Id);`
`        ``}`
`    ``}`

`    ``foreach (var n in nodes)`
`    ``{`
`        ``if (!parentIds.Contains(n.Id))`
`        ``{`
`            ``leafIds.Add(n.Id);`
`        ``}`
`    ``}`

`    ``GetSum``3``Helper(rootId, leafIds, dict, parentToChildrenIds, result);`

`    ``return result;`
`}`

`private int GetSum``3``Helper(int nodeId, HashSet<int> leafs, Dictionary<int, Node<int>> dict, Dictionary<int, List<int>> parentToChildrenIds, Dictionary<int, int> result)`
`{`
`    ``if (leafs.Contains(nodeId))`
`    ``{`
`        ``result.Add(nodeId, dict[nodeId].Value);`
`        ``return dict[nodeId].Value;`
`    ``}`

`    ``List<int> children = parentToChildrenIds[nodeId];`
`    ``int sum = dict[nodeId].Value;`
`    ``foreach (var cid in children)`
`    ``{`
`        ``sum += GetSum``3``Helper(cid, leafs, dict, parentToChildrenIds, result);`
`    ``}`

`    ``result.Add(nodeId, sum);`

`    ``return sum;`
`}`