leetcode-bt

272. Closest Binary Search Tree Value II.py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    """
    Problem Clarifiaction:
        the answer we return, order dose not matter. For example, [3,4] and [4,3] both are accepted.
    Thought Process:
        Inorder + Sort
        sort them based on the key which is abs(n.val - target), distance to the target.
        
        Inoder + PQ
            using a PQ with size k to maintian top k elements.
            pq[0] = smallest one inside
            since our goal is to find top k smalles node based on key = abs(r.val - target). we put negative before put into pq.
            As known as, we maintain top k smallest elements
        
        Quickselect:
            step1: get inoder 
            step2: get hashmap, take abs(n.val-targe) as key and node.val as val.
            step3: find k th smallest key
            step4: return node whose key less than k th smallest key
              
    """
    def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:
        """
        T:O(nlogn)
        S:O(n)
        """
        self.inorder = []
        def dfs(r):
            if r:
                dfs(r.left)
                self.inorder.append((r.val, abs(r.val-target)))
                dfs(r.right)
        
        dfs(root)
        
        self.inorder = sorted(self.inorder, key=itemgetter(1))
        
        return [n[0] for n in self.inorder[:k]]
    
    def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:
        """
        T:O(nlogk)
        S:O(n)
        """
        self.heap = []
        def dfs(r):
            if r:
                dfs(r.left)
                key = -abs(r.val-target)
                heapq.heappush(self.heap, (key, r.val))
                if len(self.heap) > k:
                    _,_ = heapq.heappop(self.heap)
                dfs(r.right)
                
                
        dfs(root)
        return [n for _, n in self.heap]
    
    def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:
        self.inorder = []
        def dfs(r):
            if r:
                dfs(r.left)
                self.inorder.append((r.val, abs(r.val-target)))
                dfs(r.right)
        
        dfs(root)