给定二叉搜索树的根结点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
这个难度不大,递归的简单运用。
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public static int sum;
public int RangeSumBST(TreeNode root, int L, int R) {
Solution obj = new Solution();
sum = 0;
obj.dfs(root , L , R);
return sum;
}
public void dfs(TreeNode root, int L, int R){
if (root != null){
if (L <= root.val && root.val <= R){
sum = sum + root.val;
}
if ( L < root.val ){
dfs(root.left, L, R);
}
if ( root.val < R){
dfs(root.right, L, R);
}
}
}
}
网友评论