java - 如何在java中递归添加计数？

Question

我正在使用二叉搜索树来保存用户输入的字符串。我想获得与给定字符串范围匹配的字符串总数。但是，我当前的代码无法正确添加字符串数。

我正在使用递归来帮助我计算 start 和 end 范围内的字符串数。例如，它通过 count 两次，但我的最终输出是 1 而不是 2。这是我的代码:

private int matchQuery(BST T, String START, String END, int count) {
        if (T == null) return count;

        // Go left of tree
        matchQuery(T.left, START, END, count);

        if(T.key != null && withinStartRange(T.key, START)) {
            count++;                       
        }

        // Go right of tree
        return matchQuery(T.right, START, END, count); 
    }

Answer 1

我认为 count 参数对 Bloodworth 方法没有用，因为他每次都取消它......

我会去

private int matchQuery(BST bst, String start, String end) {
    if (bst == null) return 0;

    int count = 0;
    if (bst.key != null && withinRange(bst.key, start, end)) count++; 

    count +=  matchQuery(bst.right, start, end);
    count += matchQuery(bst.left, start, end); 

    return count;    
}

我还修复了一些细节(命名约定等)。这可行，但是这没有考虑数据结构的属性。事实上，当你在一个特定的节点上时，你知道它左边的所有节点都比它低，而它右边的所有节点都比它高。因此，有时您可以在知道某些节点超出范围时阻止自己探索它们。 我假设在他下面的代码中我们总是有 node.left.key < node.key < node.right.key .我还假设范围包括两端

// I assume start <= end has already been checked
private int matchQuery(BST bst, String start, String end) {
    if (bst == null) return 0;
    if (bst.key == null) return matchQuery(bst.left, start, end) + matchQuery(bst.right, start, end);

    int count = 0;

    int compareToStart = bst.key.compareTo(start);
    int compareToEnd = bst.key.compareTo(end);

    if (compareToStart > 0) count += matchQuery(bst.left, start, end);
    if (compareToEnd < 0) count +=  matchQuery(bst.right, start, end);   
    if (compareToStart >= 0 && compareToEnd <= 0) count++;
    return count;    
}