How to free all trie node to avoid memory leak?


  • 0
    9

    Here is my AC code by using C.

    My problem is: how to free all trie node to avoid memory leak?

    Thanks a lot .

    #define SIZE 26
    
    struct TrieNode 
    {
        int value;  // 非0表示该节点为一个word的最后一个字符
        struct TrieNode *children[SIZE];
    };
    
    
    struct TrieNode* trieCreate() 
    {
        struct TrieNode *newNode = (struct TrieNode *)malloc(sizeof(struct TrieNode));
        int i;
        if(newNode != NULL)
        {
            newNode->value = 0;
            for(i = 0; i < SIZE; i++)
            {
                newNode->children[i] = NULL;
            }
        }
        return newNode;
    }
    
    
    void insert(struct TrieNode* root, char* word) 
    {
        if(root == NULL || word == NULL || strlen(word) == 0)
            return;
        int len = strlen(word);
        struct TrieNode *p = root;
        int i, j;
        
        root->value ++;
        for(i = 0; i < len; i++)
        {
            j = word[i]-'a';
            if(p->children[j] == NULL)
            {
                p->children[j] =  trieCreate();  
            }
            p = p->children[j];
        }
        p->value = root->value;
    }
    
    
    bool search(struct TrieNode* root, char* word) 
    {
        if(root == NULL || word == NULL || word[0] == '\0')
            return false;
            
        struct TrieNode *p = root;
        int i, j;
        int len = strlen(word);
        
        for(i = 0; i < len; i++)
        {
            j = word[i]-'a';
            if(p->children[j] == NULL)
            {
                return false;
            }
            p = p->children[j];
        }
        
        if(p->value > 0)
            return true;
        else
            return false;
    }
    
    bool startsWith(struct TrieNode* root, char* prefix) 
    {
        if(root == NULL || prefix == NULL || prefix[0] == '\0')
            return false;
            
        struct TrieNode *p = root;
        int i, j;
        int len = strlen(prefix);
        
        for(i = 0; i < len; i++)
        {
            j = prefix[i]-'a';
            if(p->children[j] == NULL)
            {
                return false;
            }
            p = p->children[j];
        }
        return true;
    }
    
    
    void trieFree(struct TrieNode* root)    // 怎么free所有节点?
    {
        if(root != NULL)
        {
            int i;
            for(i = 0; i < SIZE; i++)
            {
                if(root->children[i] != NULL)
                {
                    free(root->children[i]);
                }
            }
            free(root);
        }
    }
    
    // Your Trie object will be instantiated and called as such:
    // struct TrieNode* node = trieCreate();
    // insert(node, "somestring");
    // search(node, "key");
    // trieFree(node);

  • 0
    C

    I have bool isLeaf when doing insert(). but you can do it without it. use recursive to free all the children before free the parent node.

        void trieFreeChildren(struct TrieNode* node)
        {
           int i;
        
           if (node->isLeaf == false)
           {
              for (i=0;i<26;i++)
              {
                 if (node->children[i] != NULL)
                    trieFreeChildren(node->children[i]);
              }
           }
        
           if (node != NULL)
           {
              free(node);
           }
        
        }
        
        /** Deallocates memory previously allocated for the TrieNode. */
        void trieFree(struct TrieNode* root) {
            trieFreeChildren(root);
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.