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;}
};