[递归] 938. 二叉搜索树的范围和

给定二叉搜索树的根结点 root，返回 L 和 R（含）之间的所有结点的值的和（即树中  X>=L&&X<=R 的X值的和）。

 

初始解法，全部遍历递归

class Solution {
public:
    int rangeSumBST(TreeNode* root, int L, int R) {
        int sum=0;
        if(root->val>=L&&root->val<=R)
        {
            sum+=root->val;
        }
        if(root->left!=nullptr)
        {
            sum+=rangeSumBST(root->left,L,R);
        }
         if(root->right!=nullptr)
        {
            sum+=rangeSumBST(root->right,L,R);
        }
        return sum;
    }
};

 

另一种递归，时间反而比上面的长一点。

class Solution {
public:
    int rangeSumBST(TreeNode* root, int L, int R) {
        if(root==nullptr)
        {
            return 0;
        }
            

        if(root->val<L)
        {
            return rangeSumBST(root->right,L,R);
        }
        if(root->val>R)
        {
            return rangeSumBST(root->left,L,R);
        }
        return root->val+rangeSumBST(root->right,L,R)+rangeSumBST(root->left,L,R);
    }
};