> For the complete documentation index, see [llms.txt](https://wentao-shao.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wentao-shao.gitbook.io/leetcode/binary-tree/938.range-sum-of-bst.md).

# 938.Range-Sum-of-BST

## 938. Range Sum of BST

## 题目地址

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

## 题目描述

```
Given the root node of a binary search tree, return the sum of values of all nodes with value between L and R (inclusive).

The binary search tree is guaranteed to have unique values.

Example 1:
Input: root = [10,5,15,3,7,null,18], L = 7, R = 15
Output: 32
Example 2:

Input: root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
Output: 23

Note:
The number of nodes in the tree is at most 10000.
The final answer is guaranteed to be less than 2^31.
```

## 代码

### Approach #1 DFS

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int ans;
  public int rangeSumBST(TreeNode root, int L, int R) {
        ans = 0;
    dfs(root, L, R);
    return ans;
  }

  private void dfs(TreeNode node, int L, int R) {
    if (node != null) {
      if (node.val >= L && node.val <= R) {
        ans += node.val;
      } 
      // use if not else if
      if (L < node.val) {
        dfs(node.left, L, R);
      } 
      if (node.val < R) {
        dfs(node.right, L, R);
      }
    }
  }
}
```

### Approach #2 Iterative

```java
class Solution {
  public int rangeSumBST(TreeNode root, int L, int R) {
    int ans = 0;
    Stack<TreeNode> stack = new Stack();
    stack.push(root);
    while (!stack.isEmpty()) {
      TreeNode node = stack.pop();
      if (node != null) {
        if (L <= node.val && node.val <= R) {
          ans += node.val;
        }
        if (L < node.val) {
          stack.push(node.left);
        }
        if (node.val < R) {
          stack.push(node.right);
        }
      }
    }
    return ans;
  }
}
```