Python BST范围求和函数返回异常，局部变量使用问题排查

你的代码核心问题是没有累加左右子树的递归结果：
你在调用dfs(root.left)和dfs(root.right)时，只是执行了递归函数，但完全没有把它们返回的子树范围和加到当前的c变量里。这导致每次递归只返回当前节点符合条件的值，完全忽略了左右子树的贡献，结果自然不正确。

修正后的基础版本 #

只需要把左右子树的递归返回值累加到c中即可：

class Solution:
    def rangeSumBST(self, root, low: int, high: int) -> int:
        def dfs(root):
            if root is None:
                return 0
            c = 0
            if low <= root.val <= high:
                c += root.val
            # 加上左右子树的范围和
            c += dfs(root.left)
            c += dfs(root.right)
            return c
        return dfs(root)

利用BST特性优化（可选） #

因为二叉搜索树的左子树所有节点值都小于当前节点，右子树所有节点值都大于当前节点，我们可以做剪枝优化，减少不必要的遍历：

• 如果当前节点值小于low，左子树的所有节点肯定都小于low，直接跳过左子树，只遍历右子树
• 如果当前节点值大于high，右子树的所有节点肯定都大于high，直接跳过右子树，只遍历左子树

优化后的代码：

class Solution:
    def rangeSumBST(self, root, low: int, high: int) -> int:
        def dfs(root):
            if root is None:
                return 0
            if root.val < low:
                return dfs(root.right)
            if root.val > high:
                return dfs(root.left)
            return root.val + dfs(root.left) + dfs(root.right)
        return dfs(root)

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