Help needed in problem Delete Nodes And Return Forest

Revision en2, by parvezaalam786, 2020-09-12 13:05:05

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;
	}
};
Tags #tree, #postorder

History

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