0938. 二叉搜索树的范围和【简单】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 利用 BST 性质剪枝

1. 📝 题目描述

• leetcode

给定二叉搜索树的根结点 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

---

提示：

• 树中节点数目在范围 [1, 2 * 10^4] 内
• 1 <= Node.val <= 10^5
• 1 <= low <= high <= 10^5
• 所有 Node.val 互不相同

2. 🎯 s.1 - 利用 BST 性质剪枝

js

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} low
 * @param {number} high
 * @return {number}
 */
var rangeSumBST = function (root, low, high) {
  if (!root) return 0
  let sum = 0
  if (root.val >= low && root.val <= high) sum += root.val
  // 利用 BST 性质剪枝：左子树只有在根值大于 low 时可能包含合法值
  if (root.val > low) sum += rangeSumBST(root.left, low, high)
  // 右子树只有在根值小于 high 时可能包含合法值
  if (root.val < high) sum += rangeSumBST(root.right, low, high)
  return sum
}

• 时间复杂度：$O(n)$，最坏情况下需要访问所有节点
• 空间复杂度：$O(h)$，递归栈，$h$ 为树高

算法思路：

• 若当前节点值在区间 [low, high]，累加到答案
• 利用 BST 性质剪枝：
  • 仅当 root.val > low 时递归左子树（左侧可能仍有 ≥ low 的值）
  • 仅当 root.val < high 时递归右子树（右侧可能仍有 ≤ high 的值）
• 通过剪枝避免无效子树遍历，平均更快