leetcode 938. 二叉搜索树的范围和

题目描述

给定二叉搜索树的根结点 root,返回 L 和 R(含)之间的所有结点的值的和。
二叉搜索树保证具有唯一的值。

示例 1:
输入:root = [10,5,15,3,7,null,18], L = 7, R = 15
输出:32

示例 2:
输入:root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
输出:23

提示:

  1. 树中的结点数量最多为 10000 个。
  2. 最终的答案保证小于 2^31。

题解

二叉搜索树的左边小于根,右边大于根,根值root.ValL,R之间的就是我们要加上的值

示例代码(go)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rangeSumBST(root *TreeNode, L int, R int) int {
res := 0
if root == nil {
return res
}
if root.Val >= L && root.Val <= R {
res += root.Val
}
if root.Val > L {
res += rangeSumBST(root.Left, L, R)
}
if root.Val < R {
res += rangeSumBST(root.Right, L, R)
}
return res
}