江苏省建设工程网站,网站目录权限设置 user,金华网站建设seo,百度的特点和优势删点成林【LC1110】 给出二叉树的根节点 root#xff0c;树上每个节点都有一个不同的值。 如果节点值在 to_delete 中出现#xff0c;我们就把该节点从树上删去#xff0c;最后得到一个森林#xff08;一些不相交的树构成的集合#xff09;。 返回森林中的每棵树。你可以按…删点成林【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 {// 后序 如果根节点要删除那么把左右节点放入结果集中SetInteger del;ListTreeNode res;public ListTreeNode 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}(nm) O(nm) n n n为二叉树的节点数目 m m m为to_delete的长度空间复杂度 O ( n m ) \mathcal{O}(nm) O(nm)
