二叉树范围查询递归异常：当前节点未切换至左子节点问题排查

核心bug原因 #

你的递归函数recIRV里，遍历左右子节点时错误地使用了root.getLeftChild()和root.getRightChild()，而非当前传入的节点R的子节点。这导致每次递归调用都回到根节点的左/右子节点，永远无法深入当前节点的子树——比如当当前节点是10时，递归调用仍传入根节点的左孩子（也就是10自己），自然不会切换到2。

修正后的代码 #

结合二叉搜索树的特性，我们可以优化遍历逻辑：无需遍历所有节点，根据当前节点键与key1、key2的比较结果，决定是否遍历左/右子树，既提升效率，又保证前序遍历顺序（先处理当前节点，再左子树，再右子树）。

public ArrayList<KeyValuePair<K, V>> inRangeValues(K key1, K key2) {
    ArrayList<KeyValuePair<K, V>> result = new ArrayList<>();
    recIRV(result, key1, key2, root);
    return result;           
}

public void recIRV(ArrayList<KeyValuePair<K, V>> result, K key1, K key2, BinaryTreeNode<MapEntry<K,V>> currentNode) {
    if (currentNode == null) {
        return;
    }
    
    int compareKey1 = keyComparator.compare(currentNode.getValue().getKey(), key1);
    int compareKey2 = keyComparator.compare(currentNode.getValue().getKey(), key2);
    
    // 前序遍历：先处理当前节点，符合范围则加入结果
    if (compareKey1 >= 0 && compareKey2 < 0) {
        result.add(currentNode.getValue());
    }
    
    // 二叉搜索树特性：当前节点键 >= key1时，左子树可能存在符合条件的节点
    if (compareKey1 >= 0) {
        recIRV(result, key1, key2, currentNode.getLeftChild());
    }
    
    // 二叉搜索树特性：当前节点键 < key2时，右子树可能存在符合条件的节点
    if (compareKey2 < 0) {
        recIRV(result, key1, key2, currentNode.getRightChild());
    }
}

测试验证 #

针对测试用例inRangeValues(20,51)：

1. 先处理根节点50，50在[20,51)范围内，加入结果。
2. 50 >=20，遍历左子树10：10 <20，不在范围内；10 <51，但10 <20，左子树无需遍历，转而遍历右子树23。
3. 23在[20,51)范围内，加入结果；23 >=20，遍历左子树（为空）；23 <51，遍历右子树（为空）。
4. 回到根节点，50 <51，遍历右子树56：56 >=51，不在范围内，且56 >=51，右子树无需遍历，左子树为空。
   最终结果为[50, 23]，符合预期。

内容的提问来源于stack exchange，提问作者Dead Fox