是否可以將二叉搜索樹的節點添加到哈希集或散列圖

Question

我們可以將BST的節點放入HashMap或HashSet中嗎？如果是的話，我們如何遍歷BST。在我解決TWO SUM BST時出現這個疑問。

Answer 1

是的，你可以。二叉搜索樹具有與其他任何數據相似的數據，並且該數據可以存儲在Java中的任何其他類型的集合中。在我告訴你如何遍歷BST之前，讓我解釋一下你不知道的情況。

二叉搜索樹是一種組織數據的方式。頂層節點通常被稱爲根節點，任何小於它的數據都將被放在它的左邊，任何大於它的數據都將被放在它的右邊。這些被稱爲它的孩子，另一個節點被稱爲父親。例如，如果你的root是2，那麼它將放在它的左邊，而3將放在它的右邊。但是，節點最多隻能有2個子節點，左右分支最多隻能有1個長度。如果它們相差多於一個，則需要進行一些交換。

要遍歷樹，必須先從左分支開始。隨着每個級別的下降，您必須首先檢查節點是否有左孩子。如果確實如此，那就往下走一級。繼續下去，直到沒有剩下的孩子。這意味着這是最低的價值。上升一級，把它作爲你的下一個價值。如果它有一個正確的孩子，那麼接下來一個。繼續，直到你到達根。接下來，取根。最後，用相同的邏輯遍歷右邊的分支。去第一個右邊的孩子，只有在沒有離開孩子的情況下才可以。如果是這樣，請帶走最遠的孩子。然後帶上父母。繼續下去，直到你到達最遠的正確孩子，這將是你的最高價值。

Answer 2

您可以將BinarySearchTree的節點放入HashSet或HashMap（不知道Map的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; 
    } 
}