Sums of All Subtrees | tech::interview

Sums of All Subtrees | tech::interview

给你一组Treenode，他们每个有一个id，一个parentId，一个value，让你输出所有subtree的sum of value。
注意这个是没有children node的，只有parentId。

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> GetSum3(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);

        }

    }

 

    GetSum3Helper(rootId, leafIds, dict, parentToChildrenIds, result);

 

    return result;

}

 

private int GetSum3Helper(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 += GetSum3Helper(cid, leafs, dict, parentToChildrenIds, result);

    }

 

    result.Add(nodeId, sum);

 

    return sum;

}

http://www.1point3acres.com/bbs/thread-114594-1-1.html
Read full article from Sums of All Subtrees | tech::interview