力扣labuladong——一刷day67

本文主要是介绍力扣labuladong——一刷day67，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

前言
一、力扣582.杀掉进程
二、力扣536.从字符串生成二叉树

前言

二叉树的递归分为「遍历」和「分解问题」两种思维模式，这道题需要用到「遍历」的思维模式。

一、力扣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();}
}