Help needed in problem Delete Nodes And Return Forest

Revision en3, by parvezaalam786, 2020-09-12 13:10:52

Hello Codeforces!

I was solving this problem and got confused in pointers and references.

Problem : Delete Nodes And Return Forest

Method: By postorder traversal

We call the postorder traversal from the root and will check if the root is to be deleted. If yes, then we will push the left child and right child if they exist into our answer and then delete the root node. We will do the same for all nodes recursively.

The below solution gives me wrong answer.

But by changing:

void Helper(TreeNode* root, unordered_map<int, bool> &seen)


into

void Helper(TreeNode* &root, unordered_map<int, bool> &seen)


it got accepted.

Since pointers in cpp are passed by reference but here i needed &. I don't know why this is happening. If anyone knows this, please explain. Thanks in advance :)

class Solution {
public:
vector<TreeNode*> ans;
void Helper(TreeNode* root, unordered_map<int, bool> &seen)
{
if (root == NULL)
return;

Helper(root->left, seen);
Helper(root->right, seen);

if (seen.find(root->val) != seen.end())
{
if (root->left)
ans.push_back(root->left);
if (root->right)
ans.push_back(root->right);

root = NULL;
delete root;
}
}

vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete)
{
unordered_map<int, bool> seen;
for (int i = 0; i < to_delete.size(); i++)
{
seen[to_delete[i]] = true;
}
Helper(root, seen);
if (root)
{
ans.push_back(root);
}
return ans;
}
};


#### History

Revisions

Rev. Lang. By When Δ Comment
en3 parvezaalam786 2020-09-12 13:10:52 10 (published)
en2 parvezaalam786 2020-09-12 13:05:05 837
en1 parvezaalam786 2020-09-12 13:02:48 1705 Initial revision (saved to drafts)