public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {

TreeNode root = constructTree(pid, ppid);

List<Integer> res = new ArrayList<>();

findNode(root, kill, res);

return res;

}

private TreeNode constructTree(List<Integer> pid, List<Integer> ppid) {

Map<Integer, TreeNode> map = new HashMap<>();

int size = pid.size();

TreeNode root = null;

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

int curr = pid.get(i);

TreeNode currNode = null;

if (!map.containsKey(curr)) {

currNode = new TreeNode(curr);

map.put(curr, currNode);

} else {

currNode = map.get(curr);

}

int parent = ppid.get(i);

if (parent == 0) {

root = currNode;

} else {

TreeNode parentNode = null;

if (!map.containsKey(parent)) {

parentNode = new TreeNode(parent);

map.put(parent, parentNode);

} else {

parentNode = map.get(parent);

}

if (!parentNode.children.containsKey(curr)) {

parentNode.children.put(curr, currNode);

}

}

}

return root;

}

// BFS

private void findNode(TreeNode root, int kill, List<Integer> res) {

Queue<TreeNode> q = new LinkedList<>();

q.add(root);

while (!q.isEmpty()) {

TreeNode currNode = q.poll();

if (currNode.value == kill) {

gatherResults(currNode, res);

return;

}

for (TreeNode child: currNode.children.values()) {

q.add(child);

}

}

}

private void gatherResults(TreeNode found, List<Integer> res) {

if (found == null) return;

res.add(found.value);

for (TreeNode child: found.children.values()) {

gatherResults(child, res);

}

}

class TreeNode {

int value;

Map<Integer, TreeNode> children = new HashMap<>();

TreeNode(int x) {

this.value = x;

}

}

public List<Integer> killProcess2(List<Integer> pid, List<Integer> ppid, int kill) {

TreeNode found = findKill(pid, ppid, kill);

List<Integer> res = new ArrayList<>();

gatherResults(found, res);

return res;

}

private TreeNode findKill(List<Integer> pid, List<Integer> ppid, int kill) {

Map<Integer, TreeNode> map = new HashMap<>();

int size = pid.size();

TreeNode found = null;

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

int curr = pid.get(i);

TreeNode currNode = null;

if (!map.containsKey(curr)) {

currNode = new TreeNode(curr);

map.put(curr, currNode);

} else {

currNode = map.get(curr);

}

if (curr == kill) {

found = currNode;

}

int parent = ppid.get(i);

if (parent != 0) {

TreeNode parentNode = null;

if (!map.containsKey(parent)) {

parentNode = new TreeNode(parent);

map.put(parent, parentNode);

} else {

parentNode = map.get(parent);

}

if (!parentNode.children.containsKey(curr)) {

parentNode.children.put(curr, currNode);

}

}

}

return found;

}

/**

class Node {

int val;

List < Node > children = new ArrayList < > ();

}

public List < Integer > killProcess3(List < Integer > pid, List < Integer > ppid, int kill) {

HashMap < Integer, Node > map = new HashMap < > ();

for (int id: pid) {

Node node = new Node();

node.val = id;

map.put(id, node);

}

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

if (ppid.get(i) > 0) {

Node par = map.get(ppid.get(i));

par.children.add(map.get(pid.get(i)));

}

}

List < Integer > l = new ArrayList < > ();

l.add(kill);

getAllChildren(map.get(kill), l);

return l;

}

public void getAllChildren(Node pn, List < Integer > l) {

for (Node n: pn.children) {

l.add(n.val);

getAllChildren(n, l);

}

}

/**

public List<Integer> killProcess4(List<Integer> pid, List<Integer> ppid, int kill) {

// Kill root, return all nodes

if (kill == 0) return pid;

int n = pid.size();

Map<Integer, Set<Integer>> tree = new HashMap<>();

for (int i = 0; i < n; i++) {

if (!tree.containsKey(ppid.get(i))) {

tree.put(ppid.get(i), new HashSet<>());

}

tree.get(ppid.get(i)).add(pid.get(i));

}

List<Integer> result = new ArrayList<>();

traverse(tree, result, kill);

return result;

}

private void traverse(Map<Integer, Set<Integer>> tree, List<Integer> result, int pid) {

result.add(pid);

if (!tree.containsKey(pid)) {

return;

}

for (Integer child : tree.get(pid)) {

traverse(tree, result, child);

}

}

/**

public List < Integer > killProcess5(List < Integer > pid, List < Integer > ppid, int kill) {

HashMap < Integer, List < Integer >> map = new HashMap < > ();

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

if (ppid.get(i) > 0) {

List < Integer > l = map.getOrDefault(ppid.get(i), new ArrayList < Integer > ());

l.add(pid.get(i));

map.put(ppid.get(i), l);

}

}

Queue < Integer > queue = new LinkedList < > ();

List < Integer > l = new ArrayList < > ();

queue.add(kill);

while (!queue.isEmpty()) {

int r = queue.remove();

l.add(r);

if (map.containsKey(r))

for (int id: map.get(r))

queue.add(id);

}

return l;

}