【Leetcode Daily】1110删点成林

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个删点的列表，删除一个二叉树中所有这些点，但是把子树都放列表返回作为答案。

思路分享

• 官方题解镇楼。

  https://leetcode.cn/problems/delete-nodes-and-return-forest/solutions/2286145/shan-dian-cheng-lin-by-leetcode-solution-gy95/

• 官方的题解多了一个参数用于判断当前的节点是否为潜在的根节点，是则加到答案中。

• 而下面的题解则不要这个参数，由于删除是自底向上的，所以删除后，如果子树存在，则一定是根。所以在开始增加临时点删除，保持整个删除后将合法子节点作为答案的逻辑。

代码解答（强烈建议自行解答后再看）

• 参考题解

# 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]:
        ans = []
        tmp = TreeNode(to_delete[0], root)
        to_delete = set(to_delete)
        def dfs(root: Optional[TreeNode]):
            if not root:
                return None
            root.left = dfs(root.left)
            root.right = dfs(root.right)
            if not root.val in to_delete:
                return root
            nonlocal ans
            if root.left:
                ans.append(root.left)
            if root.right:
                ans.append(root.right)
            return None
        dfs(tmp)
        return ans