leetcode菜鸡斗智斗勇系列(9)--- Range Sum of BST
1.原题:
https://leetcode.com/problems/range-sum-of-bst/
Given the root
node of a binary search tree, return the sum of values of all nodes with value between L
and R
(inclusive).
The binary search tree is guaranteed to have unique values.
Input: root = [10,5,15,3,7,null,18], L = 7, R = 15
Output: 32
翻译:给一个BST,输出L和R之间所有的节点值的和。
2.解题思路:
这道题其实只是挂着个Binary search tree的羊头,卖的是递归的狗肉(也可以用迭代去做,但是我感觉出题者主要是想考察你递归的能力)。
其实题的意思很简单,就是让你找这个root里面所有大于L,小于R的值(包括L,R)的和。但是因为其数据结构是树状,所以必须用递归。
我们先来看看数据结构:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
很经典的树状。
然后我们来看答案,简单的递归:
class Solution
{
public int rangeSumBST(TreeNode root, int L, int R)
{
if (root == null) { return 0; }
int sum = 0;
if (root.val > L) { sum += rangeSumBST(root.left, L, R); }
if (root.val < R) { sum += rangeSumBST(root.right, L, R); }
if (root.val >= L && root.val <= R) { sum += root.val; }
return sum;
}
}
推荐阅读:
递归和迭代的区别:https://www.jianshu.com/p/32bcc45efd32
还有递归的概念
最新文章
- gcc编译器用法(自学总结)
- UWP自动填充控件AutoSuggestBox小优化
- Ajax用法总结
- JQ 全选、全不选
- 统一者管理员指南(Unifier Administration Guide)中文
- emmet使用笔记及sublime常用快捷键
- jquery返回上一页面
- js singleton
- Unity 制作虚拟手柄例子
- js代码中的parent,top和self有什么区别
- git 如何让单个文件回退到指定的版本
- 炫酷线条动画--svg
- hdu 4812 DTree (点分治)
- 使用datepicker和uploadify的冲突解决(IE双击才能打开附件上传对话框)
- 获取自定义data的几种属性
- 【算法和数据结构】_16_小算法_IntToStr: 将整型数据转换为字符串
- Java - LinkedList源码分析
- 转 一台电脑安装多个tomcat
- window XP下 php5.5+mysql+apache2+phpmyadmin安装
- [置顶]
 Ubuntu16.04+opencv3.3.0的安装配置说明