本文共 1758 字，大约阅读时间需要 5 分钟。

方法一：深度优先搜索思路

深度优先搜索是一种常用的方法来计算二叉搜索树的范围和。我们从树的根节点开始，逐层深入，直到叶子节点。以下是详细的思路分析：

以下是对应的代码实现：

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

复杂度分析

• 时间复杂度：O(n)，其中n是二叉搜索树的节点数。每个节点最多被访问一次。
• 空间复杂度：O(n)。空间复杂度主要取决于递归调用栈的深度。

方法二：广度优先搜索

广度优先搜索使用队列来实现，按层次遍历树节点。以下是详细的思路分析：

以下是对应的代码实现：

import java.util.LinkedList;
public class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        int sum = 0;
        LinkedList
   
     q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (node == null) {
                continue;
            }
            if (node.val > high) {
                q.offer(node.left);
            } else if (node.val < low) {
                q.offer(node.right);
            } else {
                sum += node.val;
                q.offer(node.left);
                q.offer(node.right);
            }
        }
        return sum;
    }
}
   

复杂度分析

• 时间复杂度：O(n)，其中n是二叉搜索树的节点数。每个节点最多被访问一次。
• 空间复杂度：O(n)。空间复杂度主要取决于队列的大小。