BST范围求和算法疑问：为何遍历条件未用<=和>=？

给定一棵二叉搜索树（BST）以及low、high两个值，需返回所有值在[low, high]闭区间内的节点值之和。以下是提供的解决方案代码：

class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        def dfs(node):
            nonlocal ans
            if node:
                if low <= node.val <= high:
                    ans += node.val
                if low < node.val:
                    dfs(node.left)
                if node.val < high:
                    dfs(node.right)

        ans = 0
        dfs(root)
        return ans

疑问 #

既然范围是包含边界的，第二个和第三个if语句中的判断条件难道不应该使用<=和>=吗？

解答 #

其实完全不用改成<=和>=，这是利用了二叉搜索树（BST）的核心特性：左子树所有节点的值都小于当前节点值，右子树所有节点的值都大于当前节点值。

• 针对第二个判断low < node.val：如果当前节点值等于low，那它的左子树里所有节点的值必然都小于low（符合BST左小右大的规则），这些节点肯定不在[low, high]区间内，所以没必要再遍历左子树，用<就足够过滤掉无意义的递归。
• 针对第三个判断node.val < high：如果当前节点值等于high，它的右子树里所有节点的值必然都大于high，同样不在目标区间内，不用浪费时间遍历右子树，用<完全合理。

这么写不仅不会漏掉符合条件的节点，反而能减少不必要的递归调用，让代码运行效率更高。

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