C++ Trie beats 93%


  • 0
    A

    class TrieNode {
    public:
    TrieNode *one;
    TrieNode *zero;
    int bit_no;

    TrieNode(int b) {
        one = NULL;
        zero = NULL;
        bit_no = b;
    }
    

    };

    class Solution {
    public:
    TrieNode *root = NULL;

    int findMaximumXOR(vector<int>& nums) {
        for(int i = 0; i < nums.size(); i ++) {
             root = makeTrie(nums[i], root, 31);
        }
    
        return findMaxXOR(root, root);
    }
    
    TrieNode* makeTrie(int num, TrieNode *root, int bit_no) {
        if(bit_no >= -1) {
            if(root == NULL) {
                root = new TrieNode(bit_no);
            }
            if(num & (1 << bit_no)) {
                root->one = makeTrie(num, root->one, bit_no - 1);
            }
            else {
                root->zero = makeTrie(num, root->zero, bit_no - 1);
            }
        }
        return root;
    }
    
    int findMaxXOR(TrieNode *a_root, TrieNode *b_root) {
        if(a_root && b_root) {
            if(((a_root->one) && (b_root->zero)) || ((a_root->zero) && (b_root->one))) {
                return max(findMaxXOR(a_root->one, b_root->zero), findMaxXOR(a_root->zero, b_root->one)) | (1 << a_root->bit_no);
            }
            else {
                return max(findMaxXOR(a_root->zero, b_root->zero), findMaxXOR(a_root->one, b_root->one));
            }
        }
        
        return 0;
    }
    

    };


Log in to reply
 

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