421. Maximum XOR of Two Numbers in an Array

Version #1 PrefixTrie + DFS

We are passing two nodes into dfs simultaneously,  if we can choose branch of different value, we choose. Otherwise choose the same value

95.05 %
class Solution {
    class TrieNode {
TrieNode[] children;
public TrieNode() {
children = new TrieNode[2];
}
}
public int findMaximumXOR(int[] nums) {
TrieNode root = new TrieNode();
for (int num : nums) {
insert(root, num);
}
return dfs(root.children[0], root.children[1] == null ? root.children[0] : root.children[1], 0);
}

private int dfs(TrieNode left, TrieNode right, int diff) {
TrieNode left0 = left.children[0], left1 = left.children[1];
TrieNode right0 = right.children[0], right1 = right.children[1];

if (left0 == null && left1 == null) {
return diff;
} else if (left0 != null && left1 != null && right0 != null && right1 != null) {
return Math.max(dfs(left0, right1, (diff << 1) + 1), dfs(left1, right0, (diff << 1) + 1));
} else if (left0 != null && right1 != null) {
return dfs(left0, right1, (diff << 1) + 1);
} else if (left1 != null && right0 != null) {
return dfs(left1, right0, (diff << 1) + 1);
} else if (left0 != null && right0 != null){
return dfs(left0, right0, (diff << 1));
} else if (left1 != null && right1 != null) {
return dfs(left1, right1, (diff << 1));
}
return 0;
}

private void insert(TrieNode root, int num) {
TrieNode curr = root;
for (int i = 31; i >= 0; i--) {
int bit = (num >> i) & 1;
if (curr.children[bit] == null) {
curr.children[bit] = new TrieNode();
}
curr = curr.children[bit];
}
}
}