题目描述

给定二叉搜索树的根结点 root，返回 L 和 R（含）之间的所有结点的值的和。

二叉搜索树保证具有唯一的值。

样例

输入：root = [10,5,15,3,7,null,18], L = 7, R = 15
输出：32

输入：root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
输出：23

注意

• 树中的结点数量最多为 10000 个。
• 最终的答案保证小于 2^31。

算法

(递归遍历) $O(n)$

1. 从根结点开始递归，如果当前结点为空，则直接返回；
2. 如果当前结点的值在 [L, R] 中，则计入 ans 中；
3. 如果 L 小于当前结点的值，则递归遍历左子树；
4. 如果当前结点的值 小于 R，则递归遍历右子树。

时间复杂度

• 每个结点最多遍历一次，故时间复杂度为 $O(n)$。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    void query(TreeNode *rt, int L, int R, int &ans) {
        if (rt == NULL)
            return;

        if (L <= rt -> val && rt -> val <= R)
            ans += rt -> val;

        if (L < rt -> val)
            query(rt -> left, L, R, ans);

        if (rt -> val < R)
            query(rt -> right, L, R, ans);

    }

    int rangeSumBST(TreeNode* root, int L, int R) {
        int ans = 0;
        query(root, L, R, ans);
        return ans;
    }
};