1、思路

• 把数组中每个数按二进制位插入到前缀树中，根节点存储最高位，每一条路径都代表一个整数；

• 对于每一个int型元素都有32位，所以前缀树的深度为32；

• 遍历数组，在前缀树中寻找与当前元素的当前位不同的路径（因为两个数在同一位的值不同，它们异或的结果才是最大的）；

• 两层循环，第一层遍历N个数，第二层遍历32位，故时间复杂度为$O(N)$；

2、代码

class Solution {
private:
    struct TrieNode     //前缀树结构体，只用来存位的值（0或1）
    {
        vector<shared_ptr<TrieNode>> children;
        TrieNode() : children(2, 0) {}
    };

    shared_ptr<TrieNode> root = make_shared<TrieNode>();

public:
    void buildTrieNode(vector<int>& nums)       //构造前缀树
    {
        for (int& num : nums)
        {
            auto node = root;
            for (int i = 31; i >= 0; -- i)      //从高位插入
            {
                int bit = (num >> i) & 1;
                if (node->children[bit] == nullptr)
                {
                    node->children[bit] = make_shared<TrieNode>();
                }

                node = node->children[bit];
            }
        }
    }

    int findMaximumXOR(vector<int>& nums) {
        buildTrieNode(nums);

        int maxXorSum = 0;
        for (int& num : nums)                   //遍历数组
        {
            auto node = root;
            int xorSum = 0;
            for (int i = 31; i >= 0; -- i)      //从高位开始寻找
            {                
                int bit = (num >> i) & 1;
                if (node->children[1 - bit] != nullptr) //尽量走与当前位相反的路径才能达到最大异或值
                {
                    xorSum = (xorSum << 1) + 1;
                    node = node->children[1 - bit];
                }
                else
                {
                    xorSum = xorSum << 1;
                    node = node->children[bit];
                }
            }

            maxXorSum = max(maxXorSum, xorSum);
        }

        return maxXorSum;
    }
};