leetcode 1110. 删点成林-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode 1110. 删点成林。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

给出二叉树的根节点 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 的方式来做，首先判断节点是否是根节点，如果结点是根节点，且不会被删除，那么就把该节点就会被添加到结果数组中，如果根节点被删除，那么其子节点会变成跟节点。文章来源地址https://www.toymoban.com/news/detail-548802.html

# 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 None
        is_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 None
        else:
            #### 如果是根节点，并且不会删除, 则添加
            if is_root:
                self.res.append(root)
            return root

    def 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] = 1
        temp = self.delNode(root, to_delete_dict, True)
        return self.res