###### tags: `Leetcode` `easy` `tree` `python` `c++`

# 938. Range Sum of BST

## [題目連結:] https://leetcode.com/problems/range-sum-of-bst/description/

## 題目:
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]```.


## 解題想法:
* 此題為給定range，求BST中符合此range之root.val之總和
* dfs按照Inorder_traversal遞迴遍歷
* 並判斷該root.val是否在range即可

## Python:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def rangeSumBST(self, root, low, high):
        """
        :type root: TreeNode
        :type low: int
        :type high: int
        :rtype: int
        """
        def dfs(root):
            if not root:
                return
            if root.val>low:
                dfs(root.left)
            if low<=root.val<=high:
                self.res+=root.val
            if root.val<high:
                dfs(root.right)
                
        self.res=0
        dfs(root)
        return self.res

## C++:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int rangeSumBST(TreeNode* root, int low, int high) {
        dfs(root,low,high);
        return res;
    }
    void dfs(TreeNode* root, int low, int high){
        if (root==nullptr)
            return;
        if (root->val>low)
            dfs(root->left,low,high);
        if (low<=root->val && root->val<=high)
            res+=root->val;
        if (root->val<high)
            dfs(root->right,low,high);
    }
private:
    int res=0;
};