---
tags: leetcode
---

# [582. Kill Process](https://leetcode.com/problems/kill-process/)
---
# My Solution
## Solution 1
### The Key Idea for Solving This Coding Question
DFS, recursion, post-order traversal
==須注意沒有 child 的 processes (也就是 `tree` 中的 leaves)。因為這些 processes 的 PID 只會出現在 `pid` 中 不會出現在 `ppid` 中。 如果漏掉第 9 ~ 11 行，建出來的 `tree` 就會沒有 leaf 。==
### C++ Code

class Solution {
public:
    vector<int> killProcess(vector<int> &pid, vector<int> &ppid, int kill) {
        unordered_map<int, vector<int>> tree;
        for (int i = 0; i < pid.size(); ++i) {
            tree[ppid[i]].push_back(pid[i]);

            auto iter = tree.find(pid[i]);
            if (iter == tree.end()) {
                tree.insert({pid[i], {}});
            }
        }

        vector<int> killedProcesses;

        dfs(tree, kill, killedProcesses);
        return killedProcesses;
    }

private:
    void dfs(unordered_map<int, vector<int>> &tree, int currKillPid, vector<int> &killedProcesses) {
        auto iter = tree.find(currKillPid);
        if (iter == tree.end()) {
            return;
        }

        vector<int> &children = iter->second;
        for (auto &nextKillPid : children) {
            dfs(tree, nextKillPid, killedProcesses);
        }
        killedProcesses.push_back(currKillPid);
    }
};

### Time Complexity
$O(n)$
$n$ is the number of nodes in the tree.
### Space Complexity
$O(H)$
$H$ is the height of the tree.
## Solution 2
### The Key Idea for Solving This Coding Question
BFS
### C++ Code

class Solution {
public:
    vector<int> killProcess(vector<int> &pid, vector<int> &ppid, int kill) {
        unordered_map<int, vector<int>> tree;
        for (int i = 0; i < pid.size(); ++i) {
            tree[ppid[i]].push_back(pid[i]);

            auto iter = tree.find(pid[i]);
            if (iter == tree.end()) {
                tree.insert({pid[i], {}});
            }
        }

        queue<int> q;
        vector<int> killedPids;

        q.push(kill);
        killedPids.push_back(kill);
        while (!q.empty()) {
            int currPid = q.front();
            q.pop();

            vector<int> &currChildren = tree[currPid];
            for (auto &nextPid : currChildren) {
                q.push(nextPid);
                killedPids.push_back(nextPid);
            }
        }

        return killedPids;
    }
};

### Time Complexity
$O(n)$
$n$ is the length of `pid`.
### Space Complexity
$O(n)$
$n$ is the length of `pid`.
# Miscellane
<!--
# Test Cases

[1,3,10,5]
[3,0,5,3]
5

[1]
[0]
1

* Time Limit Exceeded
https://leetcode.com/problems/kill-process/submissions/872319392/
-->