二叉树区间搜索求助：右侧节点检查实现遇到问题

我来帮你搞定这个二叉搜索树（BST）的区间搜索问题~ 先看看你当前代码里的几个核心问题：

• 逻辑判断有漏洞：你只处理了节点值在区间内时跳左子树，但完全忽略了右子树里也可能存在符合区间的节点；else分支直接跳右子树，没有区分节点值小于左边界或大于右边界的情况，导致很多符合条件的节点会被漏掉。
• found变量从未更新：从始至终都是false，最后返回的结果永远是错的。
• 固定大小的数组arr既容易溢出，也没用来辅助判断是否找到元素，属于冗余代码。

BST区间搜索的核心逻辑 #

BST的核心特性是左子树所有节点值 < 当前节点值 < 右子树所有节点值，利用这个特性我们可以高效剪枝：

• 如果当前节点值在[from, till]范围内：这个节点符合条件，同时需要继续遍历左、右子树，寻找其他符合条件的节点。
• 如果当前节点值 < from：左子树的节点都更小，不可能符合区间要求，直接去右子树找更大的值。
• 如果当前节点值 > till：右子树的节点都更大，不可能符合区间要求，直接去左子树找更小的值。

修正后的递归实现（逻辑更直观） #

先给你一个递归版本的代码，理解起来更简单：

private boolean search(BSTNode r, int from, int till) {
    if (r == null) {
        return false; // 空树/子树，没有找到符合条件的节点
    }
    
    int rval = r.getData();
    boolean currentMatch = rval >= from && rval <= till;
    
    // 如果当前节点符合，直接标记找到；同时继续遍历左右子树确认是否有其他节点
    if (currentMatch) {
        return true || search(r.getLeft(), from, till) || search(r.getRight(), from, till);
    } 
    // 当前节点小于左边界，去右子树找更大的值
    else if (rval < from) {
        return search(r.getRight(), from, till);
    } 
    // 当前节点大于右边界，去左子树找更小的值
    else {
        return search(r.getLeft(), from, till);
    }
}

如果你偏好迭代实现（避免递归深度问题） #

如果不想用递归，也可以用栈来实现迭代遍历：

private boolean search(BSTNode r, int from, int till) {
    if (r == null) {
        return false;
    }
    
    Stack<BSTNode> stack = new Stack<>();
    stack.push(r);
    
    while (!stack.isEmpty()) {
        BSTNode node = stack.pop();
        int val = node.getData();
        
        if (val >= from && val <= till) {
            return true; // 找到任意一个符合条件的节点就返回true
        }
        
        // 根据BST特性决定入栈哪些子节点
        if (val < from && node.getRight() != null) {
            stack.push(node.getRight());
        } else if (val > till && node.getLeft() != null) {
            stack.push(node.getLeft());
        }
    }
    
    return false;
}

额外补充 #

如果你需要收集所有符合区间的节点（而不是只判断是否存在），可以把代码里的return true改成将节点值加入列表，继续遍历直到栈空或递归结束即可。

内容的提问来源于stack exchange，提问作者Vlad Fedotov