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提示：
树中的结点数量最多为 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)
}
运行结果
总结
递归在计算机算法中，比较难懂的一块。它的处理思想就是将一个问题，分解为一个子问题，该问题具有相同的处理代码，直到终止条件。递归底层使用了栈的数据结构
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-09-21，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
