# 1110. Delete Nodes And Return Forest
Given the `root` of a binary tree, each node in the tree has a distinct value.
After deleting all nodes with a value in `to_delete`, we are left with a forest (a disjoint union of trees).
Return the roots of the trees in the remaining forest. You may return the result in any order.
**Example 1:**
Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]
**Example 2:**
Input: root = [1,2,4,null,3], to_delete = [3]
Output: [[1,2,4]]
**Constraints:**
* The number of nodes in the given tree is at most `1000`.
* Each node has a distinct value between `1` and `1000`.
* `to_delete.length <= 1000`
* `to_delete` contains distinct values between `1` and `1000`.
分析
给定一个二叉树的根节点 `root`，以及一个需要删除的节点值的列表 `to_delete`。你需要删除 `to_delete` 列表中所有值的节点。删除这些节点后，可能会形成多个独立的二叉树（一个森林）。你需要返回这个森林中所有树的根节点列表。
```
from typing import List, Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def deleteNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:
# 用于存储森林中所有树的根节点
forest = []
# 将需要删除的值放入一个集合中，方便快速查找
to_delete_set = set(to_delete)
def dfs(node: Optional[TreeNode], is_root: bool) -> Optional[TreeNode]:
"""
深度优先搜索遍历二叉树，删除指定节点并识别新的根节点。
Args:
node: 当前遍历的节点。
is_root: 一个布尔值，表示当前节点是否是某个树的根节点。
Returns:
如果当前节点被删除，则返回 None；否则返回当前节点。
"""
if not node:
return None
# 判断当前节点是否需要删除
deleted = node.val in to_delete_set
# 递归处理左右子树，并更新当前节点的左右子节点。
# 如果子节点所在的子树的根被删除，那么当前节点指向该子节点的指针会变成 None。
node.left = dfs(node.left, deleted)
node.right = dfs(node.right, deleted)
# 如果当前节点是某个树的根节点（即它的父节点被删除，或者它是原始的根节点且没有被删除），
# 并且当前节点没有被删除，那么它就是森林中的一棵树的根，将其添加到 forest 列表中。
if is_root and not deleted:
forest.append(node)
# 如果当前节点被删除，返回 None，这样它的父节点就不会再指向它了。
# 如果当前节点没有被删除，返回当前节点。
return None if deleted else node
# 从根节点开始进行深度优先搜索，初始时根节点被认为是潜在的根节点 (is_root=True)
dfs(root, True)
return forest
```
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://nataliekung.gitbook.io/ladder_code/meta-2025/1110.-delete-nodes-and-return-forest.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.