难度: Medium
给出二叉树的根节点 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、各不相同的值。运行时间: 35 ms
内存: 16.4 MB
# 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]:
to_delete = set(to_delete)
res = []
def traverse(root, parent=None):
nonlocal res
if not root:
return
left = traverse(root.left, root)
right = traverse(root.right, root)
if root.val in to_delete:
if right:
res.append(right)
if left:
res.append(left)
return
root.left = left
root.right = right
if not parent:
res.append(root)
return root
traverse(root)
return res
题解使用了递归的深度优先搜索(DFS)策略来遍历二叉树，并根据to_delete集合中的值删除相应节点。首先，将to_delete列表转换为集合以提高查找效率。定义递归函数traverse来遍历树，如果当前节点在to_delete中，则将其子节点（如果存在）加入结果列表并返回None以从树中删除当前节点；如果当前节点不在to_delete中，将其加入结果列表，并递归处理其左右子节点。递归的基准情况是遇到空节点。这样处理后，能有效地分解原树为若干不相交的子树。
时间复杂度: O(n)
空间复杂度: O(n + m)
# 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]:
to_delete = set(to_delete) # 转换为集合提高查找效率
res = [] # 存储最终的森林中各树的根节点
def traverse(root, parent=None):
nonlocal res
if not root: # 如果当前节点为空，返回None
return
left = traverse(root.left, root) # 递归处理左子树
right = traverse(root.right, root) # 递归处理右子树
if root.val in to_delete: # 如果当前节点需要删除
if right:
res.append(right) # 将右子树根节点加入结果列表
if left:
res.append(left) # 将左子树根节点加入结果列表
return # 返回None表示从树中删除当前节点
root.left = left # 更新当前节点的左孩子
root.right = right # 更新当前节点的右孩子
if not parent: # 如果当前节点是新的树的根节点
res.append(root) # 将其加入结果列表
return root # 返回当前节点，表示其未被删除
traverse(root) # 开始递归遍历树
return res # 返回结果列表
在递归函数`traverse`中，选择在确定节点需要删除之后再处理子节点的递归，是为了确保即使当前节点被删除，其子节点仍可被正确地处理并可能加入结果列表作为新的树的根节点。如果在子节点处理前就决定了节点的删除，我们将无法有效地处理并连接子节点的结果，因为子节点的状态可能依赖于它们是否成为结果列表中新的根节点。这种设计确保了算法的正确性和完整性。
在节点删除的过程中，原有的父子关系通过判断节点是否在`to_delete`列表中来断开。如果一个节点需要被删除，其子节点（如果存在）会被检查，然后根据情况加入到结果列表中作为新树的根节点。这是因为被删除的节点的子节点不再有有效的父节点。特别是，如果父节点也在`to_delete`列表中，该子节点就直接作为新的树的根节点被加入结果列表，因为它已经没有其他父节点可以连接。这样做确保了每个需要保留的子节点都能在父节点被删除的情况下独立存在。
递归函数`traverse`返回当前节点或None的设计允许在递归过程中动态地更新父节点的子节点引用。如果返回None，表示该节点被删除；如果返回当前节点，表示该节点保留在树中。这种设计有效地支持了树结构的动态修改，并确保了树的结构更新正确。然而，这种设计可能导致对树的多次遍历，特别是在每次递归调用中更新父节点的子节点引用时，可能会稍微降低效率。但在大多数情况下，这种额外的成本是可接受的，并且没有引入逻辑错误。
在算法中，一个节点被判断为新的树的根节点的依据是它不在`to_delete`列表中，并且它的父节点为空或父节点在`to_delete`列表中。在递归函数`traverse`的执行过程中，如果当前节点不需要删除并且没有有效的父节点引用（即`parent`参数为None），或者其父节点被删除（即父节点返回None），则当前节点被视为新的树的根节点并加入结果列表。这种判断方法确保只有那些没有有效父节点的节点，或是其父节点被删除的节点，才被视为新的根节点。