C++ solution using Tree/unordered_map


  • 0
    D
    class Tree {
    public:
        int id;
        int parent;
        vector<int> children;
    };
    
    class Solution {
    public:
        vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
            
            // Create Tree Structure
            unordered_map<int, shared_ptr<Tree> > created_nodes;
            int n = pid.size();
            for (int i = 0; i < n; i++) {
                shared_ptr<Tree> node;
                shared_ptr<Tree> parent_node;
                if (created_nodes.find(pid[i]) == created_nodes.end()) {
                    node = make_shared<Tree>();
                    created_nodes[pid[i]] = node;
                } else {
                    node = created_nodes[pid[i]];
                }
                if (created_nodes.find(ppid[i]) == created_nodes.end()) {
                    parent_node = make_shared<Tree>();
                    created_nodes[ppid[i]] = parent_node;
                } else {
                    parent_node = created_nodes[ppid[i]];
                }
                (parent_node->children).push_back(pid[i]);
                node->parent = ppid[i];
            }
            
            // Now use Tree
            if (created_nodes.find(kill) == created_nodes.end()) {
                return vector<int>();
            }
            vector<int> result;
            deque<int> q;
            q.push_back(kill);
            result.push_back(kill);
            while (!q.empty()) {
                shared_ptr<Tree> node = created_nodes[q.front()];
                q.pop_front();
                for (auto &child : node->children) {
                    q.push_back(child);
                    result.push_back(child);
                }
            }
            return result;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.