java - 是否可以将二叉搜索树的节点添加到哈希集或 HashMap

Question

我们可以将 BST 的节点放入 HashMap 或 HashSet 中吗？如果是这样，我们如何遍历 BST。这个疑问是在我解决 TWO SUM BST 时出现的。

Answer 1

您可以将 BinarySearchTree 的节点放入 HashSet 或 HashMap(不确定 Map 的键、值对是什么)。对于 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;
    }
}