各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 88 天。今天力扣上的每日一题是「938. 二叉搜索树的范围和」。

解题思路

本题重点：二叉搜索树，最重要性质：二叉搜索树的中序遍历是有序的。

本题没有直接使用有序的性质，而是使用了二叉搜索树的定义：每个节点的所有左子树都小于当前节点；每个节点的所有右子树都大于当前节点。

直接递归

假如题目给出的是一棵普通的二叉树，是如何求所有在 [low, high]之间的节点值的和呢？我们可以使用递归对所有节点遍历一次，前序、中序、后序均可，累加所有节点值在 [low, high]之间的节点值。

要写出递归，最基本的就是要清晰地理解并记住递归函数的定义。
比如下面的代码中，我直接用的题目给出的 rangeSumBST(root, low, high) 作为递归函数，它的含义是寻找以 root 为根节点的所有 [low, high] 范围内的节点值之和。

  • 如果当前 root 值在 [low, high] 之间就加上 root.val；
  • 然后要分别加上 root 的左、右子树中所有在 [low, high]范围内的节点之和（此时发现恰好符合 rangeSumBST() 函数的定义，于是直接调用 rangeSumBST()）。

如果没理解定义的递归函数的含义是什么，那怎么可能写出正确的递归呢？换个说法，如果没理解代码里面的每个函数或者变量的含义是什么，那怎么可能写出正确的代码呢？

代码如下：

  1. # Definition for a binary tree node.
  2. # class TreeNode(object):
  3. #     def __init__(self, val=0, left=None, right=None):
  4. #         self.val = val
  5. #         self.left = left
  6. #         self.right = right
  7. class Solution(object):
  8.     def rangeSumBST(self, root, low, high):
  9.         res = 0
  10.         if not root:
  11.             return res
  12.         res += self.rangeSumBST(root.left, low, high)
  13.         if low <= root.val <= high:
  14.             res += root.val
  15.         res += self.rangeSumBST(root.right, low, high)
  16.         return res

剪枝

上面的代码中是题目输入的是普通二叉树来进行计算的，其实题目给出的是个二叉搜索树，所以可以根据其性质进行剪枝。

  • 二叉搜索树的左子树一定比 root 小，因此如果 root.val <= low，那么不用继续搜索左子树；
  • 二叉搜索树的右子树一定比 root 大，因此如果 root.val >= high，那么不用继续搜索右子树。

经过剪枝的递归，能减少搜索的空间。因此在树特别庞大的时候，速度更快。

代码如下。

  1. # Definition for a binary tree node.
  2. # class TreeNode(object):
  3. #     def __init__(self, val=0, left=None, right=None):
  4. #         self.val = val
  5. #         self.left = left
  6. #         self.right = right
  7. class Solution(object):
  8.     def rangeSumBST(self, root, low, high):
  9.         res = 0
  10.         if not root:
  11.             return res
  12.         if root.val > low:
  13.             res += self.rangeSumBST(root.left, low, high)
  14.         if low <= root.val <= high:
  15.             res += root.val
  16.         if root.val < high:
  17.             res += self.rangeSumBST(root.right, low, high)
  18.         return res
  • 时间复杂度：$O(N)$，因为每个节点都要遍历一次；
  • 空间复杂度：$O(N)$，因为递归需要消耗系统栈。

刷题心得

树的题目，一般都可以用递归解决。在写递归的时候，一定先明白递归函数的含义，然后才能写出正确的代码。

参考资料：
938. Range Sum of BST

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

祝大家 AC 多多，Offer 多多！我们明天再见！