# Leetcode [No. 938] Range Sum of BST (EASY)

2024/1/8 Daily Challenge

## 題目

https://leetcode.com/problems/range-sum-of-bst/description/

## 思路
+ 這個解法就是用dfs去traverse每一個node
+ 如果node符合upper and lower bound，就把他加進sum

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

### 解法分析
+ time complexity: O(n)

### 執行結果

## 改良

+ 加了一些boundary condition，這樣可以少很多時間去檢查

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

### 執行結果