Python BST Range Sum 函数不返回预期结果将使用局部变量

Question

我目前正在开发一个Python函数，该函数应该计算给定范围内二叉搜索树（BST）中的值的总和。但是，我的代码似乎没有按预期工作。我希望能就可能出现的问题提供一些指导。

这是我正在使用的

Solution

类的代码：

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
            dfs(root.left)
            dfs(root.right)
            return c
        return dfs(root)

这个想法是对 BST 执行深度优先搜索 (DFS)，如果值落在给定范围内（

c

到

low

），则将值添加到总和

high

中。但是，它没有返回正确的结果。

我尝试调试此代码，但我无法找出导致问题的原因。我的实现中是否缺少一些明显的内容，或者我的代码中是否存在导致错误结果的逻辑错误？

任何解决此问题的帮助或建议将不胜感激。预先感谢！

Answer 1

您的代码正在调用

dfs

但没有对返回值执行任何操作。您应该将它们添加到总和中：

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