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

按深度优先搜索的顺序计算范围和。记当前子树根节点为 root，分以下四种情况讨论：

  • root 节点为空，返回 0。
  • root 节点的值大于 high

由于二叉搜索树右子树上所有节点的值均大于根节点的值，即均大于 high，故无需考虑右子树，返回左子树的范围和。

  • root 节点的值小于low

由于二叉搜索树左子树上所有节点的值均小于根节点的值，即均小于low，故无需考虑左子树，返回右子树的范围和。

  • root 节点的值在[low,high] 范围内

此时应返回 root 节点的值、左子树的范围和、右子树的范围和这三者之和。

代码

  1. class Solution {
  2. public:
  3.     int rangeSumBST(TreeNode *root, int low, int high) {
  4.         if (root == nullptr) {
  5.             return 0;
  6.         }
  7.         if (root->val > high) {
  8.             return rangeSumBST(root->left, low, high);
  9.         }
  10.         if (root->val < low) {
  11.             return rangeSumBST(root->right, low, high);
  12.         }
  13.         return root->val + rangeSumBST(root->left, low, high) + rangeSumBST(root->right, low, high);
  14.     }
  15. };

复杂度分析

  • 时间复杂度：O(n)，其中n 是二叉搜索树的节点数。
  • 空间复杂度：O(n)。空间复杂度主要取决于栈空间的开销。

方法二：广度优先搜索

思路

使用广度优先搜索的方法，用一个队列 qq 存储需要计算的节点。每次取出队首节点时，若节点为空则跳过该节点，否则按方法一中给出的大小关系来决定加入队列的子节点。

代码

  1. class Solution {
  2.     public int rangeSumBST(TreeNode root, int low, int high) {
  3.         int sum = 0;
  4.         Queue<TreeNode> q = new LinkedList<TreeNode>();
  5.         q.offer(root);
  6.         while (!q.isEmpty()) {
  7.             TreeNode node = q.poll();
  8.             if (node == null) {
  9.                 continue;
  10.             }
  11.             if (node.val > high) {
  12.                 q.offer(node.left);
  13.             } else if (node.val < low) {
  14.                 q.offer(node.right);
  15.             } else {
  16.                 sum += node.val;
  17.                 q.offer(node.left);
  18.                 q.offer(node.right);
  19.             }
  20.         }
  21.         return sum;
  22.     }
  23. }

复杂度分析

  • 时间复杂度：O(n)，其中n 是二叉搜索树的节点数。
  • 空间复杂度：O(n)。空间复杂度主要取决于队列的空间。
  1. class Solution {
  2.     public int rangeSumBST(TreeNode root, int low, int high) {
  3.         if (root == null) {
  4.             return 0;
  5.         }
  6.         if (root.val > high) {
  7.             return rangeSumBST(root.left, low, high);
  8.         }
  9.         if (root.val < low) {
  10.             return rangeSumBST(root.right, low, high);
  11.         }
  12.         return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
  13.     }
  14. }