Java LONG solution, beats 97%, with brief explanation


  • 0

    I know this is a long solution. but beyond my expectation, it beats 97% Java solution.

    It's also using trie, but in this question, the tree is built bit by bit, each bit could be 0 or 1, so it could be a binary tree. Left child is 0, right child is 1. From root down to the first node that has both left and right child, then compare the max XOR of the 2 children.

    case 1:
                                 left                         right 
                                 /   \                         /  \
                              a        b                      c    d
    
    should calc on  (a, d),  then calc on (b, c) , and get the max value. 
    case 2:
    
                                 left                         right 
                                 /   \                         /  \
                              a        b                      c    
    calc on (b, c)
    
    case 3:
    
                                 left                         right 
                                 /   \                            \
                              a        b                            d    
    calc on (a,d)
    
    case 4.
                          left               right
                           /                  /
                          a                  b
    
    then calc on (a, b).  Same case for the right child case.
    
    

    code as below:

    public class Solution {
        public static class TreeNode{
            int val;
            TreeNode left;
            TreeNode right;
        } 
        
        TreeNode root = new TreeNode();
        public int findMaximumXOR(int[] nums) {
            for(int n : nums){
                addToTree(n);
            }
            TreeNode node = root;
            int level = 31;
            while(node != null && (node.left == null || node.right == null)) {
                level--;
                node = node.left != null ? node.left : node.right;
            }
            
            return node == null ? 0 : diffXor(node.left, node.right, level);
        }
        
        public int diffXor(TreeNode nl, TreeNode nr, int level){
            if(nl == null || nr == null || level < 0) {
                return 0;
            }
            int v = nl.val != nr.val ? 1 << level : 0;
            int max = 0;
            boolean crossFound = false;
            if(nl.left != null && nr.right != null) {
                crossFound = true;
                max = diffXor(nl.left, nr.right, level - 1);
            }
            if(nl.right != null && nr.left != null) {
                crossFound = true;
                max = Math.max(max, diffXor(nl.right, nr.left, level - 1));
            }
            
            if(!crossFound){
                if(nl.left != null && nr.left != null) {
                    max = diffXor(nl.left, nr.left, level - 1);
                } else if(nl.right != null && nr.right != null) {
                    max = diffXor(nl.right, nr.right, level - 1);
                }
            }
            return v + max;
        }
        
        public void addToTree(int num){
            TreeNode node = root;
            for(int i = 31; i >= 0; i--){
                int v = num & (1 << i);
                if(v == 0) {
                    if(node.left == null) {
                        node.left = new TreeNode();
                        node.left.val = 0;
                    }
                    node = node.left;
                } else {
                    if(node.right == null){
                        node.right = new TreeNode();
                        node.right.val = 1;
                    }
                    node = node.right;
                }
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.