给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。

示例

示例 1：

输入：root = [10,5,15,3,7,null,18], low = 7, high = 15
输出：32

示例 2：

输入：root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
输出：23

题解

遍历二叉树，判断节点的值是否落在区间中，累加。这里可以根据搜索二叉树的性质，左子节点的值小于该节点的值，右子节点的值大于该节点的值。所以当节点的值小于 low 时，就不用遍历该节点的左子节点，但值大于 high 时也不需要遍历该节点的右子节点

  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val, left, right) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.left = (left===undefined ? null : left)
  6.  *     this.right = (right===undefined ? null : right)
  7.  * }
  8.  */
  9. /**
  10.  * @param {TreeNode} root
  11.  * @param {number} low
  12.  * @param {number} high
  13.  * @return {number}
  14.  */
  15. var rangeSumBST = function(root, low, high) {
  16.     let sum = 0
  18.     const run = node => {
  19.         if (node.val >= low && node.val <= high) {
  20.             sum += node.val
  21.         }
  22.         if (node.left && node.val > low) {
  23.             run(node.left)
  24.         }
  25.         if (node.right && node.val < high) {
  26.             run(node.right)
  27.         }
  28.     }
  30.     run(root)
  31.     return sum
  32. };

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/range-sum-of-bst
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。