Easy

题目描述

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

示例 1：

输入：root = [10,5,15,3,7,null,18], low = 7, high = 15
输出：32
解释：值为 7、10 和 15 的结点在范围 [7, 15] 内。7 + 10 + 15 = 32。

示例 2：

输入：root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
输出：23
解释：值为 6、7 和 10 的结点在范围 [6, 10] 内。6 + 7 + 10 = 23。

提示：

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

解题思路

这道题要求计算二叉搜索树中值在指定范围内的所有节点值的和。关键是要利用二叉搜索树的性质来优化遍历过程。

基本思路： 使用深度优先搜索遍历整个树，对于每个节点，判断其值是否在范围内，如果在则加到结果中。

优化思路： 利用BST的性质进行剪枝：

  • 如果当前节点值小于 low，那么其左子树的所有节点都小于 low，无需遍历左子树
  • 如果当前节点值大于 high，那么其右子树的所有节点都大于 high，无需遍历右子树
  • 只有当前节点值在范围内时，才需要同时遍历左右子树

这样的剪枝可以显著减少不必要的遍历，特别是当范围相对较小时。

推荐解法： 使用递归的深度优先搜索，结合BST性质进行剪枝，代码简洁且效率高。

迭代解法： 也可以使用栈进行迭代遍历，思路类似，但代码相对复杂一些。

代码实现

class Solution {
public:
    int rangeSumBST(TreeNode* root, int low, int high) {
        if (!root) return 0;
        
        int sum = 0;
        if (root->val >= low && root->val <= high) {
            sum += root->val;
        }
        
        if (root->val > low) {
            sum += rangeSumBST(root->left, low, high);
        }
        
        if (root->val < high) {
            sum += rangeSumBST(root->right, low, high);
        }
        
        return sum;
    }
};

class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        if not root:
            return 0
        
        total = 0
        if low <= root.val <= high:
            total += root.val
        
        if root.val > low:
            total += self.rangeSumBST(root.left, low, high)
        
        if root.val < high:
            total += self.rangeSumBST(root.right, low, high)
        
        return total

public class Solution {
    public int RangeSumBST(TreeNode root, int low, int high) {
        if (root == null) return 0;
        
        int sum = 0;
        if (root.val >= low && root.val <= high) {
            sum += root.val;
        }
        
        if (root.val > low) {
            sum += RangeSumBST(root.left, low, high);
        }
        
        if (root.val < high) {
            sum += RangeSumBST(root.right, low, high);
        }
        
        return sum;
    }
}

var rangeSumBST = function(root, low, high) {
    if (!root) return 0;
    
    let sum = 0;
    if (root.val >= low && root.val <= high) {
        sum += root.val;
    }
    
    if (root.val > low) {
        sum += rangeSumBST(root.left, low, high);
    }
    
    if (root.val < high) {
        sum += rangeSumBST(root.right, low, high);
    }
    
    return sum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(N)，其中 N 是树中节点的数量。最坏情况下需要访问所有节点，但由于剪枝，平均情况会更好
空间复杂度O(H)，其中 H 是树的高度。递归调用栈的深度等于树的高度，最坏情况为 O(N)，平衡树为 O(log N)