Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * 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);
- }
- }
Advertisement
