LeetCode "Word Search II"

Trie, again.

class TrieNode {
public:
    // Initialize your data structure here.
    TrieNode() : prev(nullptr), c(0), bIsLast(false)
    {
    }
    TrieNode(char vc) : prev(nullptr), c(vc), bIsLast(false)
    {
    }
public:
    char c;
    bool bIsLast;
    TrieNode *prev;
    map<char, TrieNode> childMap;
};

class Trie {
public:
    Trie() 
    {
        root = new TrieNode();
    }
    
    ~Trie()
    {
        if (root)
            delete root;
    }
    
    // Inserts a word into the trie.
    void insert(string s) {
        TrieNode *r = root;
        for (int i = 0; i < s.length(); i++)
        {
            if (r->childMap.find(s[i]) == r->childMap.end())
            {
                r->childMap.insert(make_pair(s[i], TrieNode(s[i])));
                r->childMap[s[i]].prev = r;
            }
            
            r = &(r->childMap[s[i]]);            
        }
        r->bIsLast = true;
    }

    // Returns if the word is in the trie.
    bool search(string key) {
        TrieNode *r = root;
        for (int i = 0; i < key.length(); i++)
        {
            if (r->childMap.find(key[i]) == r->childMap.end())
            {
                return false;
            }

            r = &(r->childMap[key[i]]);
        }

        return r->bIsLast;
    }
    TrieNode * searchByChar(char c, TrieNode *p)
    {
        if (p->childMap.find(c) != p->childMap.end())
            return &p->childMap[c];
        return nullptr;
    }

    TrieNode* root;
};


class Solution {
    set<string> ret;
    void go(vector<vector<char>>& board, Trie &trie, TrieNode *pTrie, int x, int y)
    {
        char oc = board[y][x];
        board[y][x] = 0;

        TrieNode *p = trie.searchByChar(oc, pTrie);
        if(p)
        {
            if(p->bIsLast)
            {
                string tmp;
                TrieNode *pp = p;
                while(pp)
                {
                    if(pp->c != 0)
                        tmp = pp->c + tmp;
                    pp = pp->prev;
                }
                ret.insert(tmp);
            }

            if((x - 1) >= 0 && board[y][x - 1] != 0)
            {
                go(board, trie, p, x - 1, y);
            }
            if((x + 1) < board[0].size() && board[y][x + 1] != 0)
            {
                go(board, trie, p, x + 1, y);
            }
            if((y - 1) >= 0 && board[y - 1][x] != 0)
            {
                go(board, trie, p, x, y - 1);
            }
            if((y + 1) < board.size() && board[y + 1][x] != 0)
            {
                go(board, trie, p, x, y + 1);
            }
        }

        board[y][x] = oc;
    }
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        Trie trie;
        //    Build Trie
        for(auto &w : words)
            trie.insert(w);

        //
        for(int i = 0; i < board[0].size(); i ++)
        for(int j = 0; j < board.size(); j ++)
            go(board, trie, trie.root, i, j);

        vector<string> reta;
        for(auto &w:ret)
            reta.push_back(w);
        return reta;
    }
};