LeetCode1110 删点成林

发表于 | 分类于 |
字数统计: 676 | 阅读时长 ≈ 3

链接: https://leetcode-cn.com/problems/delete-nodes-and-return-forest

题意

给出二叉树的根节点 root，树上每个节点都有一个不同的值。
如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。

解法

这道题乍看之下没什么难度，写起来才发现并不好做
题意很简单，如果节点在to_delete中出现，则将其父节点于其之间的指向断开
但问题在于如果找到父节点以及如何进行结果的维护
解法一是自己想的，主要是使用一个哑节点指向根节点，每次递归的时候传入父节点，如果当前节点需要删除则断开指针
最后处理根节点的

第二种解法是题解中学到的，每次处理一个节点，每次处理左右子树，并将结果返回
修改左右子树的指向，处理完后再进行结果的维护
如果当前节点在删除列表中，则判断左右节点是否为空，如果不为空则加入结果
这里我之前有个疑问，这里不需要判断子节点是否要删除吗
后来发现由于左右子树已经处理过了，如果子节点在删除列表中，则已经被置为null了

仔细体会，加深对递归的理解和运用能力

代码

解法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<TreeNode*> ans;
    unordered_map<int, int> mp;
    void solve(TreeNode* root, TreeNode* preNode, int mode) {
        if (root == nullptr) return;
        if (mp[root -> val] == 1) {
            if (mode)
                preNode -> right = nullptr;
            else
                preNode -> left = nullptr;
            if (root -> left && mp[root -> left -> val] == 0) 
                ans.push_back(root -> left);
            if (root -> right && mp[root -> right -> val] == 0)
                ans.push_back(root -> right);
        }
        solve(root -> left, root, 0);
        solve(root -> right, root, 1);
    }
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
        for (int i: to_delete) {
            mp[i] = 1;
        }
        if (!mp[root -> val])
            ans.push_back(root);
        TreeNode* dummy = new TreeNode(0, root, nullptr);
        solve(dummy -> left, dummy, 0);
        return ans;       
    }
};

解法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    vector<TreeNode*> ans;
    unordered_map<int, int> mp;
    TreeNode* solve(TreeNode* root) {
        if (!root) return root;
        root -> left = solve(root -> left); // 递归处理左子树
        root -> right = solve(root -> right); // 递归处理右子树
        if (mp[root -> val]) {
            // 如果左子节点在to_delete中 此时已经被置为nullptr
            if (root -> left) { 
                ans.push_back(root -> left);
            }
            if (root -> right) {
                ans.push_back(root -> right);
            }
            root = nullptr;
        }
        return root;

    }
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
        for (int i: to_delete) {
            mp[i] = 1;
        }
        // 判断根节点
        if (!mp[root -> val])
            ans.push_back(root);
        solve(root);
        return ans;        
    }
};