Closest Binary Search Tree Value II

Problem Id: 272 Difficulty: Hard Tag: Stack Tag: Tree


Intuition

Using a queue (deque in python3 could do pop and popleft in time O(1)).

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from collections import deque


class Solution:
    def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:
        if k == 0:
            return []

        self.result = deque([])
        self.size = k
        self.target = target
        self._dfs(root)
        return self.result

    def _dfs(self, node):
        if node is None:
            return
        self._dfs(node.left)

        if len(self.result) < self.size:
            self.result.append(node.val)
        elif abs(node.val - self.target) < abs(self.result[0] - self.target):
            self.result.popleft()
            self.result.append(node.val)

        self._dfs(node.right)