网站工程师平均工资优化设计卷子答案

给出二叉树的根节点 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]]

leetcode链接：https://leetcode.cn/problems/delete-nodes-and-return-forest

思路：
采用 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 __init__(self):self.res = []def delNode(self, root, to_delete_dict, is_root):if root == None:return Noneis_del = root.val in to_delete_dict### 如果 root 节点被删除, 那么其左右子节点都是根节点root.left = self.delNode(root.left, to_delete_dict, is_del)root.right = self.delNode(root.right, to_delete_dict, is_del)if is_del:return Noneelse:#### 如果是根节点，并且不会删除, 则添加if is_root:self.res.append(root)return rootdef delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:if root == None:return []to_delete_dict = {}for x in to_delete:to_delete_dict[x] = 1temp = self.delNode(root, to_delete_dict, True)return self.res