【算法】【二叉树,DFS,哈希集合,分类讨论】力扣1110. 删点成林

发布于:2024-05-22 ⋅ 阅读:(39) ⋅ 点赞:(0)

1110. 删点成林


【算法】力扣【二叉树,DFS,哈希集合,分类讨论】1110. 删点成林

题目描述

给出二叉树的根节点 root,树上每个节点都有一个不同的值。如果节点值在 to_delete 中出现,我们就把该节点从树上删去,最后得到一个森林(一些不相交的树构成的集合)。返回森林中的每棵树。你可以按任意顺序组织答案。

示例 1:

在这里插入图片描述

输入:root = [1,2,3,4,5,6,7], to_delete = [3,5]

输出:[[1,2,null,4],[6],[7]]

解释:

  • 节点3被删除后,子节点6和7成为新的树的根节点。
  • 节点5被删除后,子节点4成为新的树的根节点。

示例 2:

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

输出:[[1,2,4]]

解释:

  • 节点3被删除后,没有新的树产生,剩余的树仍然是[1,2,4]

输入输出示例解释

  • 输入:
    • root为二叉树的根节点
    • to_delete为需要删除的节点值的列表
  • 输出:
    • 森林中每棵树的根节点列表

思路解析

核心思想

我们需要遍历二叉树,判断每个节点是否需要被删除。根据分类讨论:

  1. 如果当前节点需要被删除:

    • 移除当前节点与父节点的连接
    • 递归处理其左右子树
  2. 如果当前节点不需要被删除:

    • 如果父节点被删除,则当前节点是新树的根节点,加入结果集
    • 递归处理其左右子树

算法步骤

  1. 初始化:将to_delete列表转化为集合,方便O(1)时间复杂度判断。
  2. 深度优先搜索(DFS)
    • 递归遍历二叉树。
    • 根据当前节点是否需要删除,决定是否断开与父节点的连接。
    • 根据父节点是否被删除,判断当前节点是否为新树的根节点。
  3. 返回结果:最终返回森林中的所有树的根节点。

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n),其中 n n n为二叉树的节点数,每个节点遍历一次。
  • 空间复杂度: O ( n ) O(n) O(n),递归调用栈的深度为树的高度,最坏情况下为 O ( n ) O(n) O(n)

代码实现

# 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]:
        
        """
        遍历二叉树在所难免,每个节点非删即不删,因此,我们先从分类讨论开始思考。

        如果当前节点要被删除,则:
            移除当前节点与上一个节点的连接

        否则:
            检查上一个节点是否被删除:
                如果上一个节点被删除,那么当前节点就是森林中的一棵树的根节点。
                否则,当前节点就不是根节点
        """
        
        def dfs(fa: TreeNode, node: TreeNode, is_del: bool):
            if node is None:
                return
            
            # 保留父节点是否需要被删除这一信息
            fa_is_del = is_del
            
            # 获取当前节点是否需要被删除这一信息
            is_del = node.val in to_delete

            if is_del:
                # 如果当前节点需要删除,则断开与其父节点的连接
                if node == fa.left:
                    fa.left = None
                elif node == fa.right:
                    fa.right = None
            else:
                # 否则,根据父节点是否被删除,确定当前节点是否为一个子树的根节点
                if fa_is_del:
                    # 父节点被删除,当前节点是根节点
                    ans.append(node)
            
            # 递归遍历左右子树
            dfs(node, node.left, is_del)
            dfs(node, node.right, is_del)

        ans = []
        to_delete = set(to_delete)  # 转为哈希集合,以O(1)的时间判断每个节点是否需要删除。
        
        # 特殊情况:如果根节点不为空且根节点不在删除列表中,需要将根节点作为结果的一部分
        if root and root.val not in to_delete:
            ans.append(root)
        
        dfs(TreeNode(), root, True)
        
        return ans

总结

本题通过DFS遍历二叉树,结合分类讨论的方法,逐步删除指定节点并生成新的森林。该算法有效地处理了节点删除后树结构的调整问题,并通过哈希集合优化删除判断的时间复杂度,最终实现了高效的解决方案。