【每日一题Day368】LC421数组中两个数的最大异或值 | 字典树

class Solution {
    class TrieNode{
        TrieNode[] next = new TrieNode[2];
    }
    TrieNode root = new TrieNode();
    public int findMaximumXOR(int[] nums) {
        TrieNode root;
        int res = 0;
        for (int num : nums){
            add(num);
            res = Math.max(search(num) ^ num, res);
        }
        return res;
    }
    public void add(int x){
        TrieNode p = root;
        for (int i = 31; i >= 0; i--){
            int u = (x >> i) & 1;
            if (p.next[u] == null) p.next[u] = new TrieNode();
            p = p.next[u];
        }
    } 
    public int search(int x){
        int res = 0;
        TrieNode p = root;
        for (int i = 31; i >= 0; i--){
            int u = (x >> i) & 1, v = 1 - u; 
            if (p.next[v] != null) {
                res |= (v << i);
                p = p.next[v];
            }else {
                res |= (u << i);
                p = p.next[u];
            }         
        }
        return res;
    }
}