421. Maximum XOR of Two Numbers in an Array

https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/description/
Solution 1. Get the max XOR for each num using TRIE searching after the tree is built.
Solution 2. Search the tree after the tree is built.
class Solution {
    struct TreeNode {
        TreeNode* l;
        TreeNode* r;
        TreeNode(): l(nullptr), r(nullptr) {};
    };
public:
    int findMaximumXOR(vector<int>& nums) {
        if(nums.size()<2) return 0;
        int b = 30;
        TreeNode* root = getTree(nums, b), *node = root;
        while(node && !(node->l && node->r)) {
            b--;
            if(node->l) node = node->l;
            else node = node->r;
        }
        if(b==-1) return 0;
        int res = 0;
        dfs(node->l, node->r, b, res, 1<<b);
        return res;
    }
    void dfs(TreeNode* nl, TreeNode* nr, int b, int& res, int s) {
        if(b==-1) {
            if(s>res) res = s;
            return;
        }
        if(!nl || !nr) return;
        b--;
        if(nl->l && nr->r || nl->r && nr->l) {
            dfs(nl->l, nr->r, b, res, s|(1<<b));
            dfs(nl->r, nr->l, b, res, s|(1<<b));
        }
        else {
            dfs(nl->l, nr->l, b, res, s);
            dfs(nl->r, nr->r, b, res, s);
        }
    }
    TreeNode* getTree(vector<int>& nums, int b) {
        TreeNode* root = new TreeNode(), *node;
        for(int n : nums) {
            int k = 1<<b;
            node = root;
            while(k) {
                if(k&n) {
                    if(!node->r) node->r = new TreeNode();
                    node = node->r;
                }
                else {
                    if(!node->l) node->l = new TreeNode();
                    node = node->l;
                }
                k >>= 1;
            }
        }
        return root;
    }
};

648. Replace Words

https://leetcode.com/problems/replace-words/description/
Solution 1. Trie search
class Solution {
#define NAL 26
    struct trieNode {
        trieNode* child[NAL] = {nullptr};
        bool isEnd = false;
    };
    void insert(trieNode*root, string& key) {
        trieNode* p = root;
        for(int i=0; i<key.size(); i++) {
            if(p->child[key[i]-'a'] == nullptr) {
                p->child[key[i]-'a'] = new trieNode;
            }
            p = p->child[key[i]-'a'];
            if(p->isEnd == true) return;
        }
        p->isEnd = true;
    }
    int search(trieNode*root, string& key) {
        trieNode* p = root;
        for(int i=0; i<key.size(); i++) {
            if(p->isEnd == true){ return i; }
            if(p->child[key[i]-'a'] == nullptr) return 0;
            p = p->child[key[i]-'a'];
        }
        return 0;
    }
public:
    string replaceWords(vector<string>& dict, string sentence) {
        trieNode* root = new trieNode;
        for(string &s : dict) {
            insert(root, s);
        }
        string res = "", word;
        istringstream iss(sentence);
        while(iss>>word) {
            cout<<endl;
            int len = search(root, word);
            if(len) res += " " + word.substr(0,len);
            else res += " " + word;
        }
        return res.substr(1);
    }
};