提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
前言
二叉树的递归分为「遍历」和「分解问题」两种思维模式,这道题需要用到「遍历」的思维模式。
一、力扣582.杀掉进程
class Solution {
public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
// 构建多叉树,key 为父节点,value 为所有子节点的列表
HashMap<Integer, List<Integer>> tree = new HashMap<>();
for (int i = 0; i < pid.size(); i++) {
int child = pid.get(i);
int parent = ppid.get(i);
tree.putIfAbsent(parent, new ArrayList<>());
tree.get(parent).add(child);
}
List<Integer> res = new LinkedList<>();
// 我这里用 BFS 算法遍历子树,删除以 kill 为根的所有子节点
Queue<Integer> q = new LinkedList<>();
q.offer(kill);
while (!q.isEmpty()) {
int cur = q.poll();
res.add(cur);
if (tree.containsKey(cur)) {
// 所有子节点入队
q.addAll(tree.get(cur));
}
}
return res;
}
}
二、力扣536.从字符串生成二叉树
class Solution {
public TreeNode str2tree(String s) {
if (s.isEmpty()) {
return null;
}
// 用栈模拟递归建树过程
Stack<TreeNode> stk = new Stack<>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
continue;
}
if (s.charAt(i) == ')') {
// 每次遇到有括号,都说明栈顶节点构建完成
stk.pop();
continue;
}
/* 开始读取数字 */
int j = i;
int num = 0, sign = 1;
if (s.charAt(j) == '-') {
sign = -1;
j++;
}
while (j < s.length()
&& s.charAt(j) <= '9' && s.charAt(j) >= '0') {
num = num * 10 + (s.charAt(j) - '0');
j++;
}
i = j - 1;
num = num * sign;
/* 数字读取完成 */
// 新建节点
TreeNode node = new TreeNode(num);
if (!stk.isEmpty()) {
// 栈顶元素永远是当前处理节点的父节点
TreeNode parent = stk.peek();
// 根据父节点的左右子节点情况组装
if (parent.left == null) {
parent.left = node;
} else {
parent.right = node;
}
}
// 新节点入栈
stk.push(node);
}
// 注意到除了整棵树的根节点之外,
// 其他的每个节点都可以找到一个有括号配对,
// 所以最后栈中一定还有一个节点,就是根节点
return stk.peek();
}
}