parvezaalam786's blog

Help needed in problem Delete Nodes And Return Forest
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;
	}
};
  • Vote: I like it
  • +20
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Pointers aren't exactly passed by reference, pointers are just numbers that show where something is. If you pass root to a function, and set it to null, it still only affects that copy of the pointer.

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Pointers can be really tricky. Never return a pointer to a variable declared inside a function, becuase it was a pointer to stack memory, and after the function ends, the memory gets discarted and you will be probably reading trash. Example:

int* foo() {
    int x = 0;
    return &x;
}

When you read from the pointer returned, you may read 0, but you may also read a bunch of garbage.

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Arre ques merese puch leta.. tere sare sare doubts toh bata deta hoon,. Blog post kahe bana dia. Thik ba?

→ Reply