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 互不相同

---

解题分析及思路：

这道题考察的是二叉树的遍历，不熟悉二叉树的遍历可以查看二叉树。

这道题有关二叉搜索树

方法：深度优先搜索

二叉搜索树在这里是一个小坑，因为无法确认某个子树的值是否全在范围内，所以仍然需要遍历整个树。

对于某个节点node

• 如果node的值在范围内，那么就加上node的值
• 依次遍历node的左子树和右子树

func rangeSumBST(root *TreeNode, low int, high int) (result int) {
	if root == nil {
		return 0
	}
	if root.Val <= high && root.Val >= low {
		result += root.Val
	}
	return rangeSumBST(root.Left, low, high) + rangeSumBST(root.Right, low, high) + result
}

复杂度：

• 时间复杂度：O(N)，其中 N 是树中的节点个数
• 空间复杂度：O(1)

执行结果：

• 执行耗时:68 ms,击败了76.92% 的Go用户
• 内存消耗:9.7 MB,击败了61.54% 的Go用户