给定均衡的BST。最小值，最大值和最大值，如何找到最小值和最大值内最大的异或值？

Question

基本上你有一个充满价值的BST。例如。 1-16 a min，max和value（10,15,3），您需要找到BST中的值和树中最小值和最大值内的给定值之间的最大异或值。

我想知道是否有办法做到这一点，而无需遍历整个树。 如果最小和最大不存在，我的方法是。

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) 
} 

基本上继续跟随产生更高异或值的节点。

问题我正在与最小值和最大值，当我把支票节点> =分钟& &节点< =最大的树将穿越很好，但是当我在范围之内来的，这是可能的我可能会把一个坏分支带到范围之外的数字。

让我解释一下。 以一个BST的这个右侧1-16

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

给出：

• 分钟= 10
• 最大= 15
• 值= 3

最大异或值为3^12=15

然而，对于我的算法，当我在13节点处，而不是将左边的树放到11处，我将右边的树放到了15（因为它试图达到16，但是这超出了范围）。

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

Answer 1

我的建议是遵循类似这样的回答另一个问题的方法：

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

虽然一个问题，这将是你不使用的事实，所有的元素都已经插入树中。

或者，也许，而不是一个二叉树，你可以构建一棵树，建模递归树，其次是上述解决方案？只是我的2美分:)