LeetCode 272: Closest Binary Search Tree Value II
Problem Description
Explanation:
The problem asks us to find the k closest elements to a given target value target in a binary search tree. To solve this problem, we can perform an in-order traversal of the binary search tree to get a sorted list of values, then find the k closest elements to the target by using a two-pointer approach.
- Perform an in-order traversal of the binary search tree to get a sorted list of values.
- Initialize two pointers
leftandrightto point to the closest elements to the target. - Iterate through the sorted list of values and update the pointers based on their distances to the target.
- Return the sublist of
kclosest elements.
Time Complexity:
- The time complexity of this approach is O(n) where n is the number of nodes in the binary search tree.
Space Complexity:
- The space complexity of this approach is O(n) for storing the sorted list of values.
:
Solutions
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public List<Integer> closestKValues(TreeNode root, double target, int k) {
List<Integer> values = new ArrayList<>();
inorderTraversal(root, values);
int left = 0, right = values.size() - 1;
List<Integer> result = new ArrayList<>();
while (k-- > 0) {
if (Math.abs(values.get(left) - target) < Math.abs(values.get(right) - target)) {
result.add(values.get(left++));
} else {
result.add(values.get(right--));
}
}
return result;
}
private void inorderTraversal(TreeNode root, List<Integer> values) {
if (root == null) return;
inorderTraversal(root.left, values);
values.add(root.val);
inorderTraversal(root.right, values);
}
}Related LeetCode Problems
Loading editor...