LeetCode-Python-421. 配列内の2つの数の最大異種または値

 
 
非空配列が与えられ、配列中の要素はa 0,a 1,a 2,...,an−1であり、0≦ai<231である.
aiとajの最大のヘテロOR(XOR)演算結果が見つかり,0≦i,j nであった.
O(n)の時間にこの問題を解決できますか.
例:

  : [3, 10, 5, 25, 2, 8]

  : 28

  :        5 ^ 25 = 28.

 
考え方:

    ：         ，      O(n)。          。
        ，      1         ，  "11111111"      "1"     128，
    “1111111”         127。                    “1” 。
   ：    ，       [31,30,…,1, 0]         ，left  0，right  1。
    int       "0110110…"，         [left,right,right,left,right,right,left…]。
   ：    ，      ，                       1。
--------------------- 
  ：hestyle 
  ：CSDN 
  ：https://blog.csdn.net/qq_41855420/article/details/88756998 
    ：         ，         ！

自分ではO(n)が思いつかないと思って、勉強してやっと分かった.
主な考え方はnumsの中のすべての数を木に建てて、全部で31位あって、もし現在の位の上で0ならば、左の子の木に行って、もし現在の位が1ならば、右の子の木に行って、歩いて終わったらこの経路の上のこの数がいくらなのかを記録します.
次に配列を線形にスキャンし、貪欲な戦略で木を下に遍歴し、貪欲なところは、現在の位置が0で右の木があれば、右の木に行きます.このように0と右の木の1異は1を得ることができ、逆に左の木に行きます.
このような貪欲な戦略の正確性は、高位異または1を優先的に保障することであり、バイナリの数では、より大きな異または値を得るために、最高位の1の重要性は他のビット1よりも高く、例えば1000は0111より大きいので、得られるのは必ず最大の異または値である.

class Solution(object):
    def findMaximumXOR(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        #  +trierTree
        root = TreeNode(-1)
        
        for num in nums:
            cur_node = root #   node
            
            for i in range(0, 32):               #  32  
                # print num, 1 <