3

基本的に、値で満たされた 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 値を生成するノードを追跡し続けます。

私が最小値と最大値で遭遇している問題は、 node>=min && node<=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 の代わりに何かを使用する必要がありますか? 値のリスト全体をトラバースせずにこれを行うことは可能ですか? ここでの前提は、1 つの値のリスト (BST に入力したもの) と、値のリストに適用する必要があるパラメーター (最小、最大、値) のリストがあることです。

4

1 に答える 1

1

私の提案は、別の質問に対するこの回答と同様のアプローチに従うことです。

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

ただし、これに関する 1 つの問題は、すべての要素が既にツリーに挿入されているという事実を使用していないことです。

あるいは、バイナリ ツリーの代わりに、再帰ツリーをモデル化したツリーを構築し、その後に上記のソリューションを適用できますか? ちょうど私の2セント:)

于 2012-03-14T05:54:44.700 に答える