【每日一题Day222】LC1110删点成林 | dfs后序

删点成林【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;}
  }
  

  • 复杂度
    • 时间复杂度：$\mathcal{O}(n+m)$，$n$为二叉树的节点数目，$m$为to_delete的长度
    • 空间复杂度：$\mathcal{O}(n+m)$