[recursion] 938. Range and of binary search tree

Given the root of the binary search tree  root, return  L  and  R（ contain ） The sum of the values of all nodes between （ In the tree   X>=L&&X<=R Of X It's worth it and ）.

 

Initial solution , All traversal recursion

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;
    }
};

 

Another kind of recursion , The time is a little longer than the above .

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);
    }
};