Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

272. Closest Binary Search Tree Value II

Time: $O(n)$

Space: $O(n)$

			


class Solution {
 public:
  vector<int> closestKValues(TreeNode* root, double target, int k) {
    deque<int> q;

    inorder(root, q);

    while (q.size() > k)
      if (abs(q.front() - target) > abs(q.back() - target))
        q.pop_front();
      else
        q.pop_back();

    return {begin(q), end(q)};
  }

 private:
  void inorder(TreeNode* root, deque<int>& q) {
    if (root == nullptr)
      return;

    inorder(root->left, q);
    q.push_back(root->val);
    inorder(root->right, q);
  }
};




			


class Solution {
  public List<Integer> closestKValues(TreeNode root, double target, int k) {
    Deque<Integer> q = new ArrayDeque<>();

    inorder(root, q);

    while (q.size() > k)
      if (Math.abs(q.peekFirst() - target) > Math.abs(q.peekLast() - target))
        q.pollFirst();
      else
        q.pollLast();

    return new ArrayList<>(q);
  }

  private void inorder(TreeNode root, Deque<Integer> q) {
    if (root == null)
      return;

    inorder(root.left, q);
    q.addLast(root.val);
    inorder(root.right, q);
  }
}




			


class Solution:
  def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:
    q = deque()

    def inorder(root: Optional[TreeNode]) -> None:
      if not root:
        return

      inorder(root.left)
      q.append(root.val)
      inorder(root.right)

    inorder(root)

    while len(q) > k:
      if abs(q[0] - target) > abs(q[-1] - target):
        q.popleft()
      else:
        q.pop()

    return list(q)