进程终止（你真的学会递归了吗？考验你的递归基础）

1.对应lintcode链接：

872 · 终止进程 - LintCode

2.题目描述：

 3.解题思路：

方法一：⭐⭐⭐

通过追溯父节点来判断一个节点的祖先节点中是否含有kill：

1.生成一个父亲表每个子进程可以通过id找到对应的父进程的id。

2.遍历子进程的数组从自己的id开始通过父亲表一直往上看能不能和kill的值一样如果一样就将其加入到答案中。

4.对应代码：

class Solution {
public:
    /**
     * @param pid: the process id
     * @param ppid: the parent process id
     * @param kill: a PID you want to kill
     * @return: a list of PIDs of processes that will be killed in the end
     *          we will sort your return value in output
     */
    vector<int> killProcess(vector<int> &pid, vector<int> &ppid, int kill) {
        // Write your code here
        unordered_map<int,int>Parent;
        //通过子进程的pid能够找到父进程的pid
        for(int i=0;i<pid.size();i++)
        {
            Parent[pid[i]]=ppid[i];
        }
        vector<int>ans{kill};//用于收集答案
        for(auto ch:pid)//遍历子进程的pid
        {
           int k=ch;
           int temp=k;
           while(k!=0)//通过父亲表开始一直往上走
           {
               if(Parent[k]==kill){
                   ans.push_back(temp);
                   break;
               }
               //获取自己的父进程的id
               k=Parent[k];
           }
        }
        return ans;
    }
    
 
};

但是了这种时间复杂度比较高下面我们来看另外一种方法:回溯

方法二⭐⭐⭐⭐⭐⭐

1.定义一个孩子表父进程通过自己的pid可以找到它所有的子进程的pid

2.dfs遍历每个子进程的子进程直到遍历结束。

对应代码：

class Solution {
public:
    /**
     * @param pid: the process id
     * @param ppid: the parent process id
     * @param kill: a PID you want to kill
     * @return: a list of PIDs of processes that will be killed in the end
     *          we will sort your return value in output
     */
    vector<int> killProcess(vector<int> &pid, vector<int> &ppid, int kill) {
        // Write your code here
        unordered_map<int,vector<int>>child;//父进程id对应它的孩子节点
        int N=ppid.size();
        for(int i=0;i<N;i++)
        {
            if(!child.count(ppid[i])){
                child[ppid[i]]=vector<int>();
            }
            child[ppid[i]].push_back(pid[i]);
        }
        vector<int>ans;
        dfs(ans,child,kill);
        return ans;
        
    }
    void dfs(vector<int>&ans,unordered_map<int,vector<int>>&child,int kill)
    {
         ans.push_back(kill);
         if(child.count(kill))//看有没有子进程的pid
         {
             for(auto x:child[kill])//遍历其孩子节点
             {
                 dfs(ans,child,x);
             }
         }    
    }
};