Medium

题目描述

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

提示：

  • 二叉树最多有 1000 个节点。
  • 每个节点都有一个在 1 到 1000 之间的不同的值。
  • to_delete.length <= 1000
  • to_delete 包含 1 到 1000 之间的不同的值。

解题思路

这道题的核心思想是通过深度优先搜索（DFS）来处理树的删除操作。

基本思路：

  1. 将待删除的节点值存入哈希表，便于快速查找
  2. 使用DFS遍历整棵树，对于每个节点判断是否需要删除
  3. 如果当前节点需要删除，则其左右子树（如果存在且不需要删除）将成为新的树根
  4. 如果当前节点不需要删除，则继续递归处理其子树

关键点分析：

  • 当一个节点被删除时，需要将其从父节点断开连接
  • 被删除节点的子树可能成为新的独立树
  • 需要正确处理根节点被删除的情况

算法步骤：

  1. 创建哈希表存储待删除的值
  2. 编写递归函数，返回处理后的节点（可能为null）
  3. 在递归中，先处理子树，再判断当前节点
  4. 如果当前节点需要删除，将其非空子树加入结果集
  5. 最后处理根节点的特殊情况

这种方法能够一次遍历完成所有删除操作，时间复杂度为O(n)。

代码实现

class Solution {
public:
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
        unordered_set<int> deleteSet(to_delete.begin(), to_delete.end());
        vector<TreeNode*> result;
        
        TreeNode* newRoot = dfs(root, deleteSet, result);
        if (newRoot) {
            result.push_back(newRoot);
        }
        
        return result;
    }
    
private:
    TreeNode* dfs(TreeNode* node, unordered_set<int>& deleteSet, vector<TreeNode*>& result) {
        if (!node) return nullptr;
        
        node->left = dfs(node->left, deleteSet, result);
        node->right = dfs(node->right, deleteSet, result);
        
        if (deleteSet.count(node->val)) {
            if (node->left) result.push_back(node->left);
            if (node->right) result.push_back(node->right);
            return nullptr;
        }
        
        return node;
    }
};

class Solution:
    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:
        delete_set = set(to_delete)
        result = []
        
        def dfs(node):
            if not node:
                return None
            
            node.left = dfs(node.left)
            node.right = dfs(node.right)
            
            if node.val in delete_set:
                if node.left:
                    result.append(node.left)
                if node.right:
                    result.append(node.right)
                return None
            
            return node
        
        new_root = dfs(root)
        if new_root:
            result.append(new_root)
        
        return result

public class Solution {
    public IList<TreeNode> DelNodes(TreeNode root, int[] to_delete) {
        HashSet<int> deleteSet = new HashSet<int>(to_delete);
        List<TreeNode> result = new List<TreeNode>();
        
        TreeNode newRoot = DFS(root, deleteSet, result);
        if (newRoot != null) {
            result.Add(newRoot);
        }
        
        return result;
    }
    
    private TreeNode DFS(TreeNode node, HashSet<int> deleteSet, List<TreeNode> result) {
        if (node == null) return null;
        
        node.left = DFS(node.left, deleteSet, result);
        node.right = DFS(node.right, deleteSet, result);
        
        if (deleteSet.Contains(node.val)) {
            if (node.left != null) result.Add(node.left);
            if (node.right != null) result.Add(node.right);
            return null;
        }
        
        return node;
    }
}

var delNodes = function(root, to_delete) {
    const deleteSet = new Set(to_delete);
    const result = [];
    
    function dfs(node) {
        if (!node) return null;
        
        node.left = dfs(node.left);
        node.right = dfs(node.right);
        
        if (deleteSet.has(node.val)) {
            if (node.left) result.push(node.left);
            if (node.right) result.push(node.right);
            return null;
        }
        
        return node;
    }
    
    const newRoot = dfs(root);
    if (newRoot) {
        result.push(newRoot);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历树中的每个节点一次，其中n为节点总数
空间复杂度O(h + m)h为树的高度（递归栈空间），m为待删除节点数量（哈希表空间）

相关题目