Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].

 

Example 1:

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32
Explanation: Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32.

 二叉搜索树可以压缩搜索空间。

class Solution {
public:
    int rangeSumBST(TreeNode* root, int low, int high) {
        // 二叉搜索树 减少搜索的次数
        int res=0;
        digui(root,res,low,high);
        return res;
        
    }
    void digui(TreeNode* node, int &res,int &low, int &high){
        if(node==nullptr) return;
        
        if(node->val>=low && node->val<=high){
            res+=node->val;
            digui(node->left,res,low,high);
            digui(node->right,res,low,high);
        }
        else if(node->val<low){
            digui(node->right,res,low,high);
        }
        else if (node->val>high){
            digui(node->left,res,low,high);
        }
        return;
    }
};