LeetCode 题解：938. 二叉搜索树的范围和，BFS，JavaScript，详细注释

2023-02-21
福建
本文字数：703 字
阅读完需：约 2 分钟

原题链接：https://leetcode.cn/problems/range-sum-of-bst/

解题思路：

对于二叉搜索树的任意节点，左子树的所有节点值都小于它的值，右子树的所有节点值都小于它的值。
使用队列进行 BFS 搜索，如果当前节点的值小于low，只要向右子树搜索。如果当前节点的值大于high只要向左子树搜索。
如果当前节点的值在[low, high]之间，就将其与子树的值相加返回

/** * @param {TreeNode} root * @param {number} low * @param {number} high * @return {number} */var rangeSumBST = function (root, low, high) {  let sum = 0 // 缓存结点值之和  let queue = [root] // 使用队列进行BFS搜索，初始值为树的根节点
  // 当队列被清空，表示搜索结束  while (queue.length) {    // 缓存当前一层的节点数量    let queueLength = queue.length
    // 将当前一层的节点清空    while (--queueLength >= 0) {      // 从队列中取出当前层的一个节点      const node = queue.shift()
      // 如果节点为空，则跳过      if (!node) {        continue      }
      // 当前节点的值小于low，它左侧的值都小于low，因此只要查找右侧节点      if (node.val < low) {        queue.push(node.right)      }      // 当前节点的值大于high，它左侧的值都大于high，因此只要查找右侧节点      else if (node.val > high) {        queue.push(node.left)      } else {        // 如果当前节点的值在[low, high]之间，就将其与子树的值加到sum        sum += node.val        // 继续向其子树搜索        queue.push(node.left)        queue.push(node.right)      }    }  }
  return sum}