938.Range Sum of BST
===
###### tags: `Easy`,`Tree`,`Binary Tree`,`DFS`,`Binary Search Tree`
[938. Range Sum of BST](https://leetcode.com/problems/range-sum-of-bst/)
### 題目描述
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:**
![](https://assets.leetcode.com/uploads/2020/11/05/bst1.jpg)
```
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.
```
**Example 2:**
![](https://assets.leetcode.com/uploads/2020/11/05/bst2.jpg)
```
Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
Output: 23
Explanation: Nodes 6, 7, and 10 are in the range [6, 10]. 6 + 7 + 10 = 23.
```
**Constraints**:
* The number of nodes in the tree is in the range [1, 2 * 10^4^].
* 1 <= `Node.val` <= 10^5^
* 1 <= `low` <= `high` <= 10^5^
* All `Node.val` are **unique**.
### 解答
#### Javascript
```javascript=
function rangeSumBST(root, low, high) {
if (root === null) return 0;
if (root.val < low) return rangeSumBST(root.right, low, high);
if (root.val > high) return rangeSumBST(root.left, low, high);
return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
}
```
```javascript=
function rangeSumBST(root, low, high) {
let sum = 0;
const stack = [root];
while (stack.length > 0) {
const node = stack.pop();
if (node === null) continue;
if (node.val >= low && node.val <= high) sum += node.val;
if (node.val > low) stack.push(node.left);
if (node.val < high) stack.push(node.right);
}
return sum;
}
```
> 多寫一個非遞迴的版本
> [name=Marsgoat][time= Dec 7, 2022]
#### Python
##### Recursion
```python=
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
if not root: return 0
elif low <= root.val <= high:
return root.val + self.rangeSumBST(root.left, low, high) + self.rangeSumBST(root.right, low, high)
else:
return self.rangeSumBST(root.left, low, high) + self.rangeSumBST(root.right, low, high)
```
##### Iterative
```python=
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
stack = [root]
res = 0
while stack:
node = stack.pop()
if low <= node.val <= high:
res += node.val
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return res
```
> [name=Kobe][time= Dec 7, 2022]
#### C#
```csharp=
public class Solution {
public int RangeSumBST(TreeNode root, int low, int high) {
if (root == null) return 0;
if (root.val < low) {
return RangeSumBST(root.right, low, high);
}
if (root.val > high) {
return RangeSumBST(root.left, low, high);
}
return root.val + RangeSumBST(root.left, low, high) + RangeSumBST(root.right, low, high);
}
}
```
> [name=Jim][time= Dec 7, 2022]
### Reference
[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)