With Map and Recursion


#1

`struct TreeNod
{
int val;
TreeNod* parent;
vector<TreeNod*> childs;
TreeNod(int val):val(val),parent(NULL){}
};

int findMaxEdge(TreeNod* root, int &maxEdge)
{
if(!root)
return 0;

vector<int> nodesInChilds;
for(int i = 0; i<root->childs.size(); i++)
    nodesInChilds.push_back(findMaxEdge(root->childs[i], maxEdge));

//! if child has even nodes the separate it from root
for(int i = 0; i<nodesInChilds.size(); i++)
{
    if(nodesInChilds[i] != 0 && nodesInChilds[i]%2 ==0)
    {
        root->childs[i] = NULL;
        nodesInChilds[i] = 0;
        maxEdge++;
    }
}

int remainingNodeCount = 0;
for(int i = 0; i<nodesInChilds.size(); i++)
    remainingNodeCount += nodesInChilds[i];

return remainingNodeCount + 1; //! +1 for root itself

}

int Solution::solve(int A, vector<vector > &B) {

//! Build tree
map<int, TreeNod*> M;

for(int i = 0; i<B.size(); i++)
{
    if(M.find(B[i][0]) == M.end())
    {
        TreeNod* node = new TreeNod(B[i][0]);
        M[B[i][0]] = node;
    }
    
    if(M.find(B[i][1]) == M.end())
    {
        TreeNod* node = new TreeNod(B[i][1]);
        M[B[i][1]] = node;
    }
    
    //! connect edge and parent
    M[B[i][0]]->childs.push_back(M[B[i][1]]);
    M[B[i][1]]->parent = M[B[i][0]];
}

//! select any node and find root
TreeNod* root = M.begin()->second;

while(root->parent)
{
    root = root->parent;
}

int maxEdge = 0;
findMaxEdge(root, maxEdge);

return maxEdge;

}
`