Day118 | 灵神 | 二叉树 | 删点成林

1110.删点成林

1110. 删点成林 - 力扣（LeetCode）

思路：

最直接的思路就是看当前结点的值是不是在要删除的列表中，在的话删除当前结点并把左右孩子加入res中

很可惜这样是错的，因为这样做只是删除了当前结点，没有改变当前结点父节点的指针，导致父节点的里面还放着我们已经delete以后的地址空间，这样做漏洞很大

class Solution {
public:
    vector<TreeNode*> res;
    unordered_set<int> s;
    void dfs(TreeNode *t)
    {
        if(t==nullptr)
            return ;
        if (s.find(t->val)!=s.end())
        {
            res.push_back(t->left);
            res.push_back(t->right);
        }
        dfs(t->left);
        dfs(t->right);
        if (s.find(t->val)!=s.end())
            delete t;
    }
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
        for (int x : to_delete) s.insert(x); 
        dfs(root);
        if (s.find(root->val)!=s.end())
            return res;
        res.push_back(root);
        return res;
    }
};

正确的做法是后序遍历，返回值是当前结点删了没删

如果当前结点该删除，那就给上层节点返回nullptr，告知父节点该节点被删了

​ 同时还要把不为空的左右孩子加入到森林中

如果当前结点没有被删除，那就给上层结点返回当前结点，表示当前结点没有被删除

完整代码：

class Solution {
public:
    vector<TreeNode*> res;
    unordered_set<int> s;
    
    TreeNode* dfs(TreeNode* node) {
        if (!node) return nullptr;
        // 先递归处理子树
        node->left = dfs(node->left);
        node->right = dfs(node->right);
        // 判断当前节点是否需要删除
        if (s.count(node->val)) {
            if (node->left) res.push_back(node->left);
            if (node->right) res.push_back(node->right);
            return nullptr; // 告知父节点指针置空
        }
        return node;
    }
    
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
        for (int x : to_delete) s.insert(x);
        root = dfs(root);
        if (root) res.push_back(root); // 处理根节点
        return res;
    }
};