数组中两个数的最大异或值

数组中两个数的最大异或值给定一个非空数组，数组中元素为 a0, a1, a2, … , an-1，其中 0 ≤ ai < 231 。

找到 ai 和aj 最大的异或 (XOR) 运算结果，其中0 ≤ i, j < n 。

你能在O(n)的时间解决这个问题吗？
示例:

输入: [3, 10, 5, 25, 2, 8]

输出: 28

解释: 最大的结果是 5 ^ 25 = 28.

题解

思路：
【Trie树】Trie树建立的思路，整数在存储时需要32bit，因此可以把整数看作为含有32字符的字符串，其中每个字符为0或1，则可以使用二叉树构建前缀树。从高位到低位进行构建，其中左结点为1，右结点为0.
【位运算找最大异或值】如何找到最大值异或，两个数异或得到一个尽可能大的数，则第一个1出现的位数越高则数越大，所以可以从最高位开始，找和它相反的数，如果存在这这个数异或即得到最大异或值，若不存在则，则继续相下找，直到找到相异的位。

class Solution {
    struct TreeNode{
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode(int _val): val(_val), left(nullptr), right(nullptr) {}
    };
public:
    int findMaximumXOR(vector<int>& nums) {
        //字典和建树都需要用到贪心算法 
        //建树 0->left 1->right
        TreeNode root(-1); 
        int max = 0;
        //先进行建树
        for(auto num : nums){
            TreeNode* ptr = &root;
            for(int i = 31; i >= 0; i--){
                if(num & (0x1 << i)){
                    if(ptr->right == nullptr){
                        ptr->right = new TreeNode(1);
                    }
                    ptr = ptr->right;
                }else{
                    if(ptr->left == nullptr){
                        ptr->left = new TreeNode(0);
                    }
                    ptr = ptr->left;
                }
            }
            ptr->left = new TreeNode(num);
        }
        //应用贪心算法，查找当前num下能产生最大异或值得组合
        for(auto num : nums){
            TreeNode* ptr = &root;
            for(int i = 31; i >=0; i--){
                if(num & (0x1 << i)){ //当前位是1，则必须查找该位为0的如果没有就走1的路
                    if(ptr->left){
                        ptr = ptr->left;
                    }else{
                        ptr = ptr->right;
                    }
                }else{
                    if(ptr->right){
                        ptr = ptr->right;
                    }else{
                        ptr = ptr->left;
                    }
                }
            }
            if((num^(ptr->left->val)) > max){
                max = (num^(ptr->left->val));
            }
        }
        return max;
 }
};