Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
leetcode-bt
# 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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.