1110. 删点成林 - Delete Nodes And Return Forest

🎯 问题描述（来源于LeetCode）

描述：
给定二叉树的根节点 root，以及一个要删除的节点值列表 to_delete。
删除所有值为 to_delete 中的节点后，剩下的节点会形成若干棵不相交的子树（森林）。
返回森林中所有子树的根节点列表（顺序任意）。

说明：

删除一个节点会将其左右子树断开，分别成为新的树。
被删除的节点本身不保留。
森林中每棵树的根节点是原树中未被删除且父节点被删除（或原根节点）的节点。

示例：

示例 1：

1
2
3

输入: root = [1,2,3,4,5,6,7], to_delete = [3,5]
输出: [[1,2,null,4],[6],[7]]
解释: 删除节点3和5后，剩下三个子树：以1为根（1-2-4），以6为根，以7为根。

示例 2：

1 2	输入: root = [1,2,4,null,3], to_delete = [3] 输出: [[1,2,4]]

💻 解题思路

思路1：DFS + 传递父节点删除状态

算法步骤

将待删除列表转为集合 to_del 以提高查找效率。
定义递归函数 dfs(node, parent_deleted)：
- 参数 node：当前遍历的节点。
- 参数 parent_deleted：布尔值，表示父节点是否被删除。
- 返回值：处理后的当前节点（若当前节点被删除则返回 None，否则返回节点本身）。
递归终止：若 node 为 None，返回 None。
判断当前节点是否被删除：cur_deleted = node.val in to_del。
判断是否加入森林：
- 如果父节点被删除（parent_deleted == True）且当前节点不被删除（cur_deleted == False），则当前节点成为新树的根，将其加入结果列表 res。
递归处理左右子树：
- node.left = dfs(node.left, cur_deleted)
- node.right = dfs(node.right, cur_deleted)
  将当前节点的删除状态传递给子节点。
返回值：
- 若当前节点被删除，返回 None，否则返回当前节点（其左右子节点已更新）。
启动递归：从根节点开始，初始父节点视为被删除（parent_deleted = True），因为根节点没有父节点，相当于其父节点被删除，这样如果根节点不被删除，它会自动加入森林。

思路1：代码实现

# 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
from typing import List, Optional

class Solution:
    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:
        to_del = set(to_delete)
        res = []
        
        def dfs(node, parent_deleted):
            if not node:
                return None
            cur_deleted = node.val in to_del
            if parent_deleted and not cur_deleted:
                res.append(node)
            node.left = dfs(node.left, cur_deleted)
            node.right = dfs(node.right, cur_deleted)
            return None if cur_deleted else node
        
        dfs(root, True)
        return res