html购物网站代码,平面设计专业哪个学校最好,网站控制板面,安阳吧1110. 删点成林
关键要点
通过O(1)时间复杂度确认节点是否需要删除 Set to_deleteSet new HashSet(); Arrays.stream(to_delete).forEach(to_deleteSet::add); 使用深度优先搜索#xff08;DFS#xff09;遍历树 node.left dfs(node.left, s, ans); node.right …
1110. 删点成林
关键要点
通过O(1)时间复杂度确认节点是否需要删除 Set to_deleteSet new HashSet(); Arrays.stream(to_delete).forEach(to_deleteSet::add); 使用深度优先搜索DFS遍历树 node.left dfs(node.left, s, ans); node.right dfs(node.right, s, ans); 当前节点处理逻辑 判断当前节点是否为待删除节点 不是则返回节点保持父子关系当前节点为待删除节点 添加左孩子、右孩子到结果集中【因为是DFS所以不用考虑放入结果集中的孩子们是否也应该删除】删除当前节点【return null;】断绝关系 代码编写 /*** 1110. 删点成林* https://leetcode.cn/problems/delete-nodes-and-return-forest/description/* param root* param to_delete* return*/public ListTreeNode delNodes(TreeNode root, int[] to_delete) {if (Objects.isNull(root) || Objects.isNull(to_delete) || to_delete.length 0) {return Collections.singletonList(root);}// 确认是否需要删除node O(1)SetInteger to_deleteSet new HashSet();Arrays.stream(to_delete).forEach(to_deleteSet::add);ListTreeNode result new ArrayList();// DFSif (!Objects.isNull(dfs(root, to_deleteSet, result))) {result.add(root);}return result;}/*** DFS-从下子节点向上父节点* param node* param s* param ans* return*/private TreeNode dfs(TreeNode node, SetInteger s, ListTreeNode ans) {if (Objects.isNull(node)) {return null;}// 左node.left dfs(node.left, s, ans);// 右node.right dfs(node.right, s, ans);if (!s.contains(node.val)) {// 当前节点不能删除保持与父节点的链接return node;}// 当前节点为待删除的节点if (!Objects.isNull(node.left)) {ans.add(node.left);}if (!Objects.isNull(node.right)) {ans.add(node.right);}// 删除当前节点断开与父节点的链接return null;}代码解析
如果根节点为空或者删除数组为空直接返回只含有根节点的列表。将待删除的节点值存入一个哈希集合 to_deleteSet 中。通过深度优先搜索DFS遍历树判断当前节点是否需要删除。如果不需要删除则递归遍历其左右子节点并更新左右子节点的链接如果需要删除则将其左右子节点加入结果集 ans 中并将当前节点删除。返回结果集 ans即删除节点后的根节点集合。
