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]