Company Tree

solution

每一个点下面都连着很多点。自己看代码吧。

cpp.sh

// Example program
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

class node {
public:
    int val;
    vector<node*> vec;
    node(int val)
    {
        this->val = val;
    }

    void add(node* p)
    {
        this->vec.push_back(p);   
    }
};

void dfs(node* root, map<node*, double>& hash)
{
    if(root == NULL || root->vec.empty())
    {
        return ;   
    }

    double sum = 0;

    for(unsigned int i = 0; i<root->vec.size(); i++)
    {
        sum += root->vec[i]->val;
        dfs(root->vec[i], hash);
    }
    hash[root] = sum/(int)root->vec.size();
}

double companytree(node* root)
{
    map<node*, double> hash;
    dfs(root, hash);

    double ret = 0;
    map<node*, double>::iterator it = hash.begin();
    for(; it != hash.end(); it++)
    {
        ret = max(ret, it->second);   
    }

    return ret;
}
int main()
{

    std::cout << "Hello, World!\n";

    node* root = new node(5);

    node* p1 = new node(1);
    root->add(p1);

    node* p2 = new node(2);
    root->add(p2);

    node* p3 = new node(3);
    root->add(p3);

    node* p4 = new node(4);
    root->add(p4);

    node* p5 = new node(5);
    root->add(p5);

    node* p6 = new node(100);
    p5->add(p6);

    cout<<companytree(root)<<endl;
    return 1;
}

code

class cnode {
public:
    int val;
    vector<cnode*> vec;
    cnode(int val)
    {
        this->val = val;
    }
    void add(cnode* node)
    {
        vec.push_back(node);
    }
};

void dfs(cnode* root, map<cnode*, double>& hash)
{
    if(root == NULL || root->vec.size() == 0)
    {
        return ;
    }

    double sum = 0;
    for(int i = 0; i < root->vec.size(); i++)
    {
        sum += root->vec[i]->val;
        dfs(root->vec[i], hash);
    }

    hash[root] = sum/root->vec.size();
}

double companytree(cnode* root)
{
    if(root == NULL)
    {
        return 0;
    }

    map<cnode*, double> hash;
    dfs(root, hash);

    map<cnode*, double>::iterator it = hash.begin();
    cnode* ret = root;
    double maxavg = hash[root];

    for(; it != hash.end(); it++)
    {
        if(it->second > maxavg)
        {
            maxavg = it->second;
            ret = it->first;
        }
    }

    return maxavg;
}

int main(int argc, const char * argv[])
{
    // insert code here...
    std::cout << "Hello, World!\n";

    cnode* root = new cnode(5);

    cnode* p1 = new cnode(1);
    root->add(p1);

    cnode* p2 = new cnode(2);
    root->add(p2);

    cnode* p3 = new cnode(3);
    root->add(p3);

    cnode* p4 = new cnode(4);
    root->add(p4);

    cnode* p5 = new cnode(5);
    root->add(p5);

    cnode* p6 = new cnode(2);
    p5->add(p6);

    cout<<companytree(root)<<endl;

    return 0;
}