938. 二叉搜索树的范围和

• 2019 年 10 月 7 日
• 筆記

题目

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

运行结果

总结

递归在计算机算法中，比较难懂的一块。它的处理思想就是将一个问题，分解为一个子问题，该问题具有相同的处理代码，直到终止条件。递归底层使用了栈的数据结构