每日一题Day222LC1110删点成林 | 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; } }
- 复杂度
- 时间复杂度: O ( n m ) \mathcal{O}(n m) O(n m), n n n为二叉树的节点数目, m m m为
to_delete
的长度 - 空间复杂度: O ( n m ) \mathcal{O}(n m) O(n m)
- 时间复杂度: O ( n m ) \mathcal{O}(n m) O(n m), n n n为二叉树的节点数目, m m m为
- 复杂度
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgfcieb
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01