前缀树之最大的异或

package com.zhang.reflection.面试.算法模版.前缀树;
/**
 * 力扣067：给定一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。
 */

public class 最大的异或 {
    Trie root=new Trie();
    static final int HIGH_BIT=30;
    class Trie{
        Trie left=null;
        Trie right=null;
    }
    public int findMaximumXOR(int[] nums){
        int n=nums.length;
        if(n==1){
            return 0;
        }
        for(int num:nums){
            add(num);
        }
        int result=0;
        for(int i=1;i<n;i++){
            result=Math.max(result,check(nums[i]));
        }
        return result;
    }
    public void add(int num){
        Trie cur=root;
        for(int i=HIGH_BIT;i>=0;i--){
            int bit=(num>>i)&1;
            if(bit==0){
                if(cur.left==null){
                    cur.left=new Trie();
                    cur=cur.left;
                }else{
                    cur=cur.left;
                }
            }else{
                if(cur.right==null){
                    cur.right=new Trie();
                    cur=cur.right;
                }else{
                    cur=cur.right;
                }
            }
        }
    }
    public int check(int num){
        Trie cur=root;
        int x=0;
        for(int i=HIGH_BIT;i>=0;i--){
            int bit=(num>>i)&1;
            if(bit==0){
                if(cur.right!=null){
                    cur=cur.right;
                    x=x*2+1;
                }else{
                    cur=cur.left;
                    x=x*2;
                }
            }else{
                if(cur.left!=null){
                    cur=cur.left;
                    x=x*2+1;
                }else{
                    cur=cur.right;
                    x=x*2;
                }
            }
        }
        return x;
    }
}