938. 二叉搜索树的范围和

暮雨

发布于 2019-09-25 02:34:26

42600

代码可运行

文章被收录于专栏：云端漫步云端漫步

运行总次数：0

代码可运行

题目

给定二叉搜索树的根结点 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

提示：

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

题解

二叉搜索树的特点是左子节点小于父节点，右子节点大于父节点。对于该题，则是求出L <= X <= R之间的节点的和

在处理树的问题，常使用递归对于递归则需要，1. 需要推导递归公式， 2. 终止条件对于该题，递归的终止条件则为当前节点为空，则返回0，终止递归递归公式：当前节点x<L, 则对右子树的和当前节点x>R, 则对左子树的和当前节点满足L<=x <= R, 则返回当前节点值 + 左子树之和 + 右子树之和得到了以上的总结，就可以很容易的写出实现的代码

代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rangeSumBST(root *TreeNode, L int, R int) int {
	if root == nil {
		return 0
	}

	if root.Val < L {
		return rangeSumBST(root.Right, L, R)
	}

	if root.Val > R {
		return rangeSumBST(root.Left, L, R)
	}

	return root.Val + rangeSumBST(root.Left, L, R) + rangeSumBST(root.Right, L, R)
}