Documenting LeetCode solving.
Celebrate 20 days completed! 🎉
Q60
297. Serialize and Deserialize Binary Tree
Hard. Tree
DFS
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
res = [] # ["1", "2", "N" ...]
def dfs(node):
if not node:
res.append("N")
return
res.append(str(node.val))
dfs(node.left)
dfs(node.right)
dfs(root)
return ",".join(res) # "1,2,N,N ..."
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
vals = data.split(",")
self.i = 0 # Global index, outside of dfs (no need to pass in)
def dfs():
if vals[self.i] == "N":
self.i += 1
return None
node = TreeNode(vals[self.i])
self.i += 1
node.left = dfs()
node.right = dfs()
return node
return dfs()
Q61
703. Kth Largest Element in a Stream
Easy (Medium actually). Heap/ priority queue.
Min heap of size k.
class KthLargest:
def __init__(self, k: int, nums: List[int]):
# Min heap of size k, the first element will be the kth largest
self.minHeap, self.k = nums, k
heapq.heapify(self.minHeap)
# Pop heap until k values in the heap
while len(self.minHeap) > self.k:
heapq.heappop(self.minHeap)
def add(self, val: int) -> int:
heapq.heappush(self.minHeap, val)
if len(self.minHeap) > self.k:
heapq.heappop(self.minHeap)
return self.minHeap[0]