内容简介：给予一颗二叉搜索树, 返回区间 L - R 之间的所有值的总和. 二叉搜索树中没有重复值.例 :因为是一颗二叉搜索树, 所以我们采用中序遍历即可得到从小到大的值, 不过既然知道区间, 那么我们可以过滤到一些没必要的查找, 如上面的例子, 查到到了节点 3, 根据二叉搜索树的规则:
给予一颗二叉搜索树, 返回区间 L - R 之间的所有值的总和. 二叉搜索树中没有重复值.
例 :
给予树, L = 3, R = 8:
5
/ \
3 6
/ \ \
2 4 8
/ / \
1 7 9
返回: 3 + 4 + 5 + 6 + 7 + 8 = 33.
解法
因为是一颗二叉搜索树, 所以我们采用中序遍历即可得到从小到大的值, 不过既然知道区间, 那么我们可以过滤到一些没必要的查找, 如上面的例子, 查到到了节点 3, 根据二叉搜索树的规则: 当前节点的所有左子树的值都比他小 , 且我们知道这棵树中没有重复值, 那么久没必要将他的左子树再进行递归判断了, 右子树同理.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int i = 0;
public int rangeSumBST(TreeNode root, int L, int R) {
if (root == null) {
return 0;
}
if (root.val > L && root.left != null) {
rangeSumBST(root.left, L, R);
}
if (root.val >= L && root.val <= R) {
i += root.val;
}
if (root.val < R && root.right != null) {
rangeSumBST(root.right, L, R);
}
return i;
}
}
Runtime: 0 ms, faster than 100.00% of Java online submissions for Range Sum of BST. Memory Usage: 43.1 MB, less than 99.61% of Java online submissions for Range Sum of BST
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
The Black Box Society
Frank Pasquale / Harvard University Press / 2015-1-5 / USD 35.00
Every day, corporations are connecting the dots about our personal behavior—silently scrutinizing clues left behind by our work habits and Internet use. The data compiled and portraits created are inc......一起来看看 《The Black Box Society》 这本书的介绍吧!
