Home > Net >  C unordered_map implementation problem previous values in map get forgotten
C unordered_map implementation problem previous values in map get forgotten

Time:06-30

In the below code why map size is always 1, it is not saving previous values of root->val in the map as I can see in stdout. I was expecting that it should remember all the values put in the map.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class FindElements {
public:

    unordered_map<int,int>mp;

    FindElements(TreeNode* root) {
        if(!root) return;
        if(root->val==-1){
            root->val=0;
        }
        mp[root->val]=1;
        
        // output
        cout<<root->val<<" "<<mp[root->val]<<" "<<mp.size()<<endl;
        
        if(root->left){
            root->left->val=2*(root->val) 1;
            FindElements(root->left);
        }
        if(root->right){
            root->right->val=2*(root->val) 2;
            FindElements(root->right);
        }
    }
    
    bool find(int target) {
        return mp[target];
    }
};
/**
 * Your FindElements object will be instantiated and called as such:
 * FindElements* obj = new FindElements(root);
 * bool param_1 = obj->find(target);
 */

enter image description here

Input:

["FindElements","find","find","find"]    
[[[-1,-1,-1,-1,-1]] , [1] , [3] , [5]]

Output:

[null,false,false,false]

Expected:

[null,true,true,false]

stdout:

0 1 1     
1 1 1     
3 1 1    
4 1 1    
2 1 1    

key,value,map-size

I was expecting that in each row map size values get increased.

leetcode problem link

CodePudding user response:

Your code looks like you make an recursive call, to make a depth first search on the tree, but in fact it does not.

Because you are not using a normal member function, but the constructor, and a constructor can not be called recursive.

The syntax that look like recursion is instead the creation of additional temporary objects which will be destroyed after tge line ends.

  • Related