LeetCode-Solutions/C++/kill-process.cpp at master · pythonpeixun/LeetCode-Solutions · GitHub

History

50 lines (45 loc) · 1.28 KB

Raw

// Time: O(n)

// Space: O(n)

// DFS solution.

class Solution {

public:

vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {

vector<int> result;

unordered_map<int, unordered_set<int>> children;

for (int i = 0; i < pid.size(); ++i) {

children[ppid[i]].emplace(pid[i]);

}

killAll(kill, children, &result);

return result;

}

private:

void killAll(int pid, unordered_map<int, unordered_set<int>>& children, vector<int> *killed) {

killed->emplace_back(pid);

for (const auto& child : children[pid]) {

killAll(child, children, killed);

}

};

// Time: O(n)

// Space: O(n)

// BFS solution.

class Solution {

public:

vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {

vector<int> result;

unordered_map<int, unordered_set<int>> children;

for (int i = 0; i < pid.size(); ++i) {

children[ppid[i]].emplace(pid[i]);

}

queue<int> q;

q.emplace(kill);

while (!q.empty()) {

const auto p = q.front(); q.pop();

result.emplace_back(p);

for (const auto& child : children[p]) {

q.emplace(child);

}

return result;

}

};

LeetCode-Solutions/C++/kill-process.cpp at master · pythonpeixun/LeetCode-Solutions · GitHub

Expand file tree

Breadcrumbs

kill-process.cpp

Latest commit

History

Breadcrumbs

kill-process.cpp

File metadata and controls