/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private List<Integer> values;
private int[] prefixSum;
public int rangeSumBST(TreeNode root, int low, int high) {
values = new ArrayList<>();
inOrder(root);
if (values.isEmpty()) return 0;
prefixSum = new int[values.size()];
int sum = 0;
for (int i = 0; i < prefixSum.length; i++) {
prefixSum[i] = sum = sum + values.get(i);
}
int left = Collections.binarySearch(values, low);
int right = Collections.binarySearch(values, high);
// Handle cases where exact values aren't found
if (left < 0) left = -(left + 1); // Insertion point
if (right < 0) right = -(right + 1) - 1; // Last index before insertion point
// if (left >= values.size() || right < 0) return 0;
// Adjust for inclusive range
if (left > 0) {
return prefixSum[right] - prefixSum[left - 1];
} else {
return prefixSum[right];
}
}
private void inOrder(TreeNode node) {
if (node == null) return;
inOrder(node.left);
values.add(node.val);
inOrder(node.right);
}
}
Comments
0 B
|0 👍
/0 👎
0 B
|👍
/👎