LeetCode 题解工作台
删点成林
给出二叉树的根节点 root ，树上每个节点都有一个不同的值。 如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。 返回森林中的每棵树。你可以按任意顺序组织答案。 示例 1： 输入： root = [1,2,3,4,5,6,7], to…
5
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们先用哈希表或者一个长度为 的数组 记录所有需要删除的节点。 接下来，设计一个函数 ，它会返回以 为根的子树中，删除所有需要删除的节点后的树的根节点。函数 的执行逻辑如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给出二叉树的根节点 root，树上每个节点都有一个不同的值。
如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。
返回森林中的每棵树。你可以按任意顺序组织答案。
示例 1：
输入：root = [1,2,3,4,5,6,7], to_delete = [3,5] 输出：[[1,2,null,4],[6],[7]]
示例 2：
输入：root = [1,2,4,null,3], to_delete = [3] 输出：[[1,2,4]]
提示：
- 树中的节点数最大为
1000。 - 每个节点都有一个介于
1到1000之间的值，且各不相同。 to_delete.length <= 1000to_delete包含一些从1到1000、各不相同的值。
解题思路
方法一：DFS
我们先用哈希表或者一个长度为 的数组 记录所有需要删除的节点。
接下来，设计一个函数 ，它会返回以 为根的子树中，删除所有需要删除的节点后的树的根节点。函数 的执行逻辑如下：
- 如果 为空，那么我们返回空；
- 否则，我们递归执行 和 ，并将返回值分别赋给 和 。如果 不需要被删除，那么我们返回 ；如果 需要被删除，那么我们分别判断 和 是否为空，如果它们不为空，那么我们将它们加入答案数组中；最后返回空。
在主函数中，我们调用 ，如果结果不为空，说明根节点不需要被删除，我们再将根节点加入答案数组中。最后返回答案数组即可。
时间复杂度 ，空间复杂度 。其中 是树的节点数。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def delNodes(
self, root: Optional[TreeNode], to_delete: List[int]
) -> List[TreeNode]:
def dfs(root: Optional[TreeNode]) -> Optional[TreeNode]:
if root is None:
return None
root.left, root.right = dfs(root.left), dfs(root.right)
if root.val not in s:
return root
if root.left:
ans.append(root.left)
if root.right:
ans.append(root.right)
return None
s = set(to_delete)
ans = []
if dfs(root):
ans.append(root)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each node is visited once. Space complexity is O(n) for the hash set storing nodes to delete and for recursion stack in the worst case of a skewed tree. |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Asks about handling child nodes of deleted parents.
- question_mark
Probes if the hash set lookup is necessary for efficiency.
- question_mark
Questions how to maintain forest roots without extra passes.
常见陷阱
外企场景- error
Forgetting to add child nodes of deleted nodes to the forest.
- error
Modifying the tree incorrectly, losing subtrees during deletion.
- error
Using repeated linear scans instead of a hash set, causing O(n^2) behavior.
进阶变体
外企场景- arrow_right_alt
Delete nodes with values in a given range instead of an explicit list.
- arrow_right_alt
Return the forest in a specific order, such as preorder traversal of roots.
- arrow_right_alt
Handle trees where duplicate values may exist, requiring careful identification.