algorithm - 范围查询-树不包含上限和/或下限

假设我有一个Binary Search Tree

        50
     /       \
    17        72
  /    \     /   \
 12    23   54   76
 /\    /     \
9 14  19     67

对不起，我画树很烂
我想返回在一定范围内的所有节点。例如

[12, 23] --> {12, 14, 17, 23, 19}

我的方法很简单
查找LCA
查找下限
while节点！=lca.parent，添加右子树
从LCA，while node！=上界，添加左子树
添加上界的上界和左子树
但是，如果树中不包含一个或两个边界怎么办。例如

[11, 72] --> {12, 14, 17, 23, 19, 50, 54, 67, 72}

我的方法看起来很相似，除了不搜索边界，而是搜索直到节点子节点超出了您的边界。因此，在找到“LCA”（不是一个真正的LCA，因为它不存在），寻找11。到了12点后，看到左边的孩子还不到11岁，就停下来。
是否有更有效的解决方案来执行此范围查询？BST并不是强制的，它看起来只是一个很好的数据结构。
当树中不包含边界时，我的方法是否有效？

最佳答案

正如@nico所建议的，您只需要一个递归算法来遍历树，而不需要关心lca。事实上，二叉树是一个二叉搜索树，允许您执行一些优化并避免遍历整个树如果节点的值低于您的下限，请不要遍历节点的左分支。

void FindNodesInBound(BSTNode node, int lowerBound, int upperBound, List<int> matches) {
    if (node != null) {
        if (node.Value >= lowerBound)
            FindNodesInBound(node.Left, lowerBound, upperBound, matches);
        if (node.Value >= lowerBound && node.Value <= upperBound)
            matches.Add(node.Value);
        if (node.Value <= upperBound)
            FindNodesInBound(node.Right, lowerBound, upperBound, matches);
    }
}