C++ [For those who didn't learn DFS yet] [Without Explicit DFS] [Tree concepts]


#1
int help(int root, unordered_map<int, vector<int>>& adj, int& ans, int p){
    if((adj[root]).size() == 1 && adj[root][0] == p){ // leaf node, p is parent node
        return 1;
    }
    int nodes = 1; // size of the current tree
    for(auto child : adj[root]){
        if(child == p)continue;
        int sz = help(child, adj, ans, root); // subtree size
        if(sz % 2 == 0){
            ans++;
        }else{
            nodes += sz;
        }
    }
    return nodes;
}
int Solution::solve(int A, vector<vector<int> > &B) {
    unordered_map<int, vector<int>> adj; // adjacency list
    for(int i = 0; i < B.size(); i++){
        adj[B[i][0]].push_back(B[i][1]);
        adj[B[i][1]].push_back(B[i][0]);
    }
    // choose root 
    int root = B[0][0];
    int ans = 0;
    int sz = help(root, adj, ans, -1); // help returns size of the tree
    return ans;
}