给定一个平衡的BST.最小值、最大值和值，如何在最小值和最大值内找到最大的Xor

Question

基本上，您有一个充满值的BST。例如1-16最小值、最大值和值（10,15,3），您需要找到BST中的值与树的最小值和最大值之间的最大xor值。

我想知道是否有一种方法可以做到这一点，而无需在整个树中进行迭代。如果min和max不存在，我的方法是。

int xor (Node curent,min,max,value,highestXor){
 1. if node == null return highestXor
 2. check node.value ^ value, if > highestXor replace.
 3. check node.left ^ value and node.right ^ value, nextNode= highest between them 
 4. xor(nextNode,min,max,value,newHighest)
}

基本上保持跟踪产生较高xor值的节点。

我在min和max中遇到的问题是，当我检查节点>=min&amp；节点<max，树会很好地遍历，但当我在范围内时，我可能会将一个坏分支带到范围外的数字。

让我解释一下。以BST 1-16 的右侧为例

      9 
    /   
  /       
5           13
           /   
         11     15
         /     /
       10  12 14  16

给定：

• 最小值=10
• 最大值=15
• 值=3

最大Xor值为3^12=15

然而，用我的算法，当我在13节点时，我不是把左边的树取到11，而是把右边的树取15（因为它试图达到16，但超出了范围）。

有人有更好的解决方案吗？我应该对BST进行不同的排序吗？我应该用什么东西而不是BST吗？是否可以在不遍历整个值列表的情况下执行此操作？这里的假设是，我将有一个值列表（我在BST中放入的值），然后是一个必须应用于值列表的参数列表（最小值、最大值、值）。

Answer 1

我的建议是采用类似于另一个问题的答案的方法：

https://stackoverflow.com/a/9320467/1015955

不过，这样做的一个问题是，您没有使用所有元素都已插入到树中的事实。

或者，你可以构建一个树来模拟递归树，而不是二叉树，然后是上面的解决方案？只有我的2美分：）