parvezaalam786's blog

By parvezaalam786, history, 8 months 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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by parvezaalam786 (previous revision, new revision, compare).

»
8 months 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.

»
8 months 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.

»
8 months 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?