938.二叉搜索树的范围和

二叉搜索树的范围和

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

解析

利用 BST 的性质，只遍历可能在范围内的节点。

var rangeSumBST = function (root, low, high) {
  if (!root) return 0;

  let sum = 0;
  const stack = [root];

  while (stack.length) {
    const node = stack.pop();
    if (node.val >= low && node.val <= high) {
      sum += node.val;
    }
    if (node.val > low && node.left) stack.push(node.left);
    if (node.val < high && node.right) stack.push(node.right);
  }

  return sum;
};

时间复杂度 O(n)，空间复杂度 O(h)，其中 h 为树的高度。