C++ tree solution beats 96.45%


  • 0
    B
    class Solution {
        struct node {
            node *left;
            node *right;
            node():left(NULL),right(NULL){}
        };
        void add2tree(node *root, int num) {
            for(int i=(sizeof(int)*8-1);i>=0;i--) {
                if(num&(1<<i)) {
                    if(!root->right) root->right = new node();
                    root=root->right;
                }
                else {
                    if(!root->left) root->left = new node();
                    root = root->left;
                }
            }
        }
        int getResult(int level, int v, node *n1, node *n2) {
            if(!n1 || !n2 || level==0) return v;
            int res = 0;
            if(n1->left && n2->right) res = max(res, getResult(level-1, v+pow(2,level-1), n1->left, n2->right));
            if(n1->right && n2->left) res = max(res, getResult(level-1, v+pow(2,level-1), n1->right, n2->left));
            if(res) return res;
            return max(getResult(level-1,v, n1->left, n2->left), getResult(level-1,v,n1->right,n2->right));
        }
    public:
        int findMaximumXOR(vector<int>& nums) {
            node *root = new node();
            for(int i:nums) add2tree(root, i);
            int level = 32;
            while(level && (!root->left || !root->right)) {
                root = root->left?root->left:root->right;
                level--;
            }
            if(level == 0) return 0;
            return getResult(level-1, pow(2,level-1), root->left, root->right);
        }
    };
    

Log in to reply
 

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