1110.删点成林

链接：1110.删点成林
难度：Medium
标签：树、深度优先搜索、数组、哈希表、二叉树
简介：给出二叉树的根节点 root，树上每个节点都有一个不同的值。如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。返回森林中的每棵树。你可以按任意顺序组织答案。

题解 1 - rust

• 编辑时间：2023-05-30
• 执行用时：4ms
• 内存消耗：2.2MB
• 编程语言：rust
• 解法介绍：同上。

use std::cell::RefCell;
use std::collections::HashSet;
use std::ops::RangeBounds;
use std::rc::Rc;
type Res = Vec<Option<Rc<RefCell<TreeNode>>>>;
fn dfs(
    res: &mut Res,
    s: &HashSet<i32>,
    node: &mut Option<Rc<RefCell<TreeNode>>>,
    pd: bool,
) -> Option<Rc<RefCell<TreeNode>>> {
    match node {
        None => None,
        Some(ref node) => {
            let mut nodeRef = node.as_ref().borrow_mut();
            let d = s.contains(&nodeRef.val);
            if !d && pd {
                res.push(Some(node.clone()));
            }
            nodeRef.left = dfs(res, s, &mut nodeRef.left, d);
            nodeRef.right = dfs(res, s, &mut nodeRef.right, d);
            if pd || d {
                None
            } else {
                Some(node.clone())
            }
        }
    }
}
impl Solution {
    pub fn del_nodes(mut root: Option<Rc<RefCell<TreeNode>>>, to_delete: Vec<i32>) -> Res {
        let mut s = std::collections::HashSet::<i32>::new();
        for v in to_delete {
            s.insert(v);
        }
        let mut res: Res = vec![];
        dfs(&mut res, &s, &mut root, true);
        res
    }
}

题解 2 - python

• 编辑时间：2023-05-30
• 执行用时：72ms
• 内存消耗：16.6MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:
        res = []
        s = set()
        for v in to_delete:
            s.add(v)
        def dfs(node: Optional[TreeNode], pd: bool):
            if node == None:
                return node
            d = node.val in s
            if not d and pd:
                res.append(node)
            node.left = dfs(node.left, d)
            node.right = dfs(node.right, d)
            return None if pd or d else node
        dfs(root, True)
        return res

题解 3 - cpp

• 编辑时间：2023-05-30
• 执行用时：12ms
• 内存消耗：13.3MB
• 编程语言：cpp
• 解法介绍：dfs遍历时，记录父节点是否已经被删除。

class Solution {
public:
    vector<TreeNode*> res;
    unordered_set<int> s;
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
        for (auto &v : to_delete) s.insert(v);
        dfs(root, true);
        return res;
    }
    TreeNode* dfs(TreeNode *node, bool pd) {
        if (!node) return node;
        bool del = s.count(node->val);
        if (!del && pd) res.push_back(node);
        node->left = dfs(node->left, del);
        node->right = dfs(node->right, del);
        if (pd || del) return nullptr;
        return node;
    }
};