删点成林【LC1110】
给出二叉树的根节点 root，树上每个节点都有一个不同的值。
如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。
返回森林中的每棵树。你可以按任意顺序组织答案。
又是一段瓶颈期
2023/5/30
- 思路遍历树时，如果当前节点需要删除，那么其孩子节点如果存在的话，那么就变成了单独的树，需要单独添加至结构集中。
- 因此，可以使用哈希表记录
to_delete中的值，快速判断某个节点是否需要删除 - 然后后序遍历该树，先将左右子树中需要删除的节点删除，然后判断父节点是否需要删除
- 如果需要删除时如果左右孩子不为空，将其放入结果集中；
- 如果父节点不需要删除，七左右子树中某些节点可能已经被删除，那么更新其左右孩子
- 最后判断根节点是否被删除，如果未被删除，那么将其放入结果集中（也可以设置假的根节点，避免重复代码）
- 实现
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { // 后序 如果根节点要删除，那么把左右节点放入结果集中 Set<Integer> del; List<TreeNode> res; public List<TreeNode> delNodes(TreeNode root, int[] to_delete) { this.del = new HashSet<>(); this.res = new ArrayList<>(); for (int d : to_delete){ del.add(d); } TreeNode newRoot = dfs(root); if (newRoot != null){ res.add(newRoot); } return res; } public TreeNode dfs(TreeNode node){ if (node == null){ return null; } node.left = dfs(node.left); node.right = dfs(node.right); if (del.contains(node.val)){// 删除当前节点 // 如果孩子节点不为空，加入结果集中 if (node.left != null){ res.add(node.left); } if (node.right != null){ res.add(node.right); } node = null; } return node; } }
复杂度
- 时间复杂度：O(n+m)，n为二叉树的节点数目，m为
to_delete的长度 - 空间复杂度：O(n+m)
