parvezaalam786's blog

By parvezaalam786, history, 4 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • +20
  • Vote: I do not like it