バイナリ検索ツリーのノードをハッシュセットまたはハッシュマップに追加することは可能ですか

Question

BSTのノードをHashMapまたはHashSetのどちらかに入れることはできますか？もしそうなら、私たちはBSTをどのようにトラバースするのですか。私はTWO SUM BSTを解決している間にこの疑いが生じました。

Answer 1

はい、できます。バイナリ検索ツリーには他のデータと同様のデータがあり、そのデータをJavaの他のタイプのコレクションに格納することができます。 BSTをどのようにトラバースするかを説明する前に、わからない場合に備えて、それが何であるかを説明しましょう。

バイナリ検索ツリーは、データを整理する方法です。一番上のノードは通常ルートと呼ばれ、それよりも小さいデータはその左に置かれ、それより大きいデータはその右に置かれます。これらはその子と呼ばれ、他のノードは親と呼ばれます。たとえば、ルートが2の場合、1は左に、3は右に配置されます。しかし、ノードは最大2つの子のみを持つことができ、左右の枝は最大でも1の長さだけ異なることができます。複数のノードが異なる場合は、いくつかのスワップを行う必要があります。

ツリーをトラバースするには、最初に左のブランチから開始する必要があります。各レベルを下げると、まずノードに左の子があるかどうかを確認する必要があります。そうであれば、1つ下の階層に進みます。残っている子供がなくなるまで下り続けてください。これはこれが最も低い値であることを意味します。 1つ上のレベルに上がって、それを次の価値にしてください。それが正しい子供を持っている場合は、次のものを取る。ルートに到達するまでこれを続けます。次に、ルートを取る。最後に、同じロジックで右ブランチをトラバースします。最初の右の子供に行って、左の子供がいない場合にのみ取る。もしそうなら、最も遠い子を取る。その後、親を取る。一番遠い子になるまでこれを続けてください。これはあなたの最高の価値です。

Answer 2

BinarySearchTreeのノードをHashSetまたはHashMapに配置することができます（マップのKey、Valueのペアリングが不明）。 HashSetの場合、私は単にBSTを順番にトラバースします。あなたが与えられた問題を解決するために、私はそのような問題に取り組んでいます：

// Returns true if the BST contains two nodes with elements that 
// sum to k, otherwise false 
public bool findTarget(TreeNode root, int k){ 
    if(root == null){ 
     throw new NullPointerException(); 
    } 
    HashSet<Integer> set = new HashSet<Integer>(); 
    return traverse(root, k, set); 
} 

// Traverses across the BST, in order, adding elements to the set 
bool traverse(Node<T> node, int k, HashSet<Node<T>> set){ 
    // If the node has a left child, traverse it first 
    if(node.left != null){ 
     return traverse(node.left, k, set); 
    } 
    // Check to see if the set contains the element that would sum 
    // with the node we're checking's element to equal k 
    if(set.contains(k-node.element)){ 
     return true; 
    } 
    // Add node's element to the set 
    set.add(node.element); 

    // If the node has a right child, traverse it after 
    if(node.right != null){ 
     return traverse(node.right, k, set); 
    } 
    else{ 
     // No two node's with elements summing k exist in the BST, 
     // since you reached the end and found nothing 
     return false; 
    } 
}