添加根值范围内的数字 returns 不正确的值

Question

我正在学习 LeetCode，这个问题让我卡住了。我得到了一个二叉搜索树的根节点，我被要求 return L 和 R 之间的所有值的总和包括：

示例：

Input: root = [10,5,15,3,7,null,18], L = 7, R = 15
Output: 32 (10+15+7)

这是我的尝试：

class Solution:

    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:
        value = 0
        
        if root.val >= L and root.val <= R:
            value += root.val
        
        return value

然而，这就是它 returning:

Your input [10,5,15,3,7,null,18] 7 15
Output     10
Expected   32

Answer 1

你停在了树的根部。递归地看树。

尝试

class Solution:
    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:
        if root is None or root.val < L or root.val > R:
            return 0
        return root.val + self.rangeSumBST(root.left, L, R) + self.rangeSumBST(root.right, L, R)

Answer 2

在 Python 中，您可以简单地使用 L <= root.val <= R.

而不是 if root.val >= L and root.val <= R

那么，还有两个条件需要定义。这将通过：

class Solution:
    def rangeSumBST(self, root, L, R):
        if not root:
            return 0

        summation = 0
        if root.val > L:
            summation += self.rangeSumBST(root.left, L, R)

        if root.val < R:
            summation += self.rangeSumBST(root.right, L, R)

        if L <= root.val <= R:
            summation += root.val

        return summation

这里是LeetCode使用栈的迭代解法：

class Solution(object):
    def rangeSumBST(self, root, L, R):
        ans = 0
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                if L <= node.val <= R:
                    ans += node.val
                if L < node.val:
                    stack.append(node.left)
                if node.val < R:
                    stack.append(node.right)
        return ans

参考资料

有关其他详细信息，您可以在其中查看 Discussion Board. There are plenty of accepted solutions with a variety of languages and explanations, efficient algorithms, as well as asymptotic time/space complexity analysis^{1, 2}。

添加根值范围内的数字 returns 不正确的值

Adding numbers within a range of root values returns incorrect value

python

algorithm

treenode

参考资料