算法1

(递归) $O(n)$

时间复杂度：遍历树的所有节点，故为O(n)
空间复杂度：递归调用栈的高度，同样也是O(n)

Python 代码

class Solution:
    def __init__(self):
        self.ans = 0

    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:

        def inorder(node):
            if not node:
                return None

            inorder(node.left)
            if low <= node.val <= high:
                self.ans += node.val
            inorder(node.right)

        inorder(root)

        return self.ans

上面的代码是没有经过剪枝的标准二叉树模板遍历代码，但通过二叉搜索树的性质，我们将root.val与[L, R]进行比较，可以省去一些递归分支。

Python 代码

class Solution:
    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
        if not root:
            return 0

        # 当root.val小于low表示，root的左子树节点值都小于low，所以答案只能在root的右子树上。
        if root.val < low:
            return self.rangeSumBST(root.right, low, high)
        # 同理，当root.val大于high表示，root的右子树节点值都大于high，所以答案只能在root的左子树上。
        elif root.val > high:
            return self.rangeSumBST(root.left, low, high)

        # 这里包含[L, R]区间的所有节点值
        return root.val + self.rangeSumBST(root.left, low, high) + self.rangeSumBST(root.right, low, high)

C++ 代码

class Solution {
public:
    int rangeSumBST(TreeNode* root, int low, int high) {
        if (!root) return 0;

        if (root->val < low) return rangeSumBST(root->right, low, high);
        if (root->val > high) return rangeSumBST(root->left, low, high);

        return root->val + rangeSumBST(root->left, low, high) + rangeSumBST(root->right, low, high);
    }
};