Aug 16, 2021

Leetcode 297 Serialize and Deserialize Binary Tree

Soru

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Örnek 1

image




Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

Örnek 2


Input: root = []
Output: []

Çözüm

  • Bir binary tree’yi string’e çeviren (serialize) ve bu string’den tekrar aynı binary tree’yi oluşturan (deserialize) iki fonksiyonu implement etmen isteniyor.
  • Tree yapısını koruyarak, kayıpsız bir şekilde bu dönüşümleri yapmak gerekiyor.
  • Örneğin, ağaçtaki null değerler (yani çocukları olmayan dallar) da string temsilinde yer almalı.

Code

class Codec:
    def serialize(self, root):
        if not root:
            return ""
        #Eğer ağacımız boşsa (yani root yoksa), boş bir string döndürürüz.
        res = []
        queue = deque([root])
        #Sonuçları tutmak için res listesi, BFS yapmak için de queue (bir deque) başlatıyoruz.
        while queue:
            node = queue.popleft()
            if node:
                res.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
            else:
                res.append("null")

        #Kuyruktan bir düğüm alıyoruz.
        #Eğer düğüm varsa:
        #Değerini listeye ekliyoruz.
        #Sol ve sağ çocuklarını kuyruğa ekliyoruz.
        #Eğer düğüm None ise "null" olarak işaretliyoruz.
        #Bu şekilde tüm ağaç katman katman (level by level) taranıyor.

        return ",".join(res)
        #Son olarak, listeyi virgülle birleştirerek string'e çeviriyoruz.

    def deserialize(self, data):
        if not data:
            return None
        #Eğer data boşsa, ağacımız da boştur, direkt None döneriz.

        nodes = data.split(",")
        root = TreeNode(int(nodes[0]))
        queue = deque([root])
        i = 1

        #data string’ini ayırıp bir listeye çeviriyoruz.
        #İlk değer kök düğümdür.
        #BFS yapmak için bir kuyruk başlatıyoruz.
        #i pointer’ı, nodes listesinde ilerlemeyi sağlar.
        
        while queue:
            node = queue.popleft()
            if nodes[i] != "null":
                node.left = TreeNode(int(nodes[i]))
                queue.append(node.left)
            i += 1

            if nodes[i] != "null":
                node.right = TreeNode(int(nodes[i]))
                queue.append(node.right)
            i += 1
        
        #Kuyruktan bir düğüm alıp, sol ve sağ çocuklarını oluşturuyoruz (eğer "null" değilse).
        #Her oluşturulan çocuğu tekrar kuyruğa ekliyoruz ki onun da alt çocuklarını kurabilelim.

        return root

Complexity

  • Time complexity (Zaman Karmaşıklığı) :
    • Serialize (Time) O(n)
    • Deserialize (Time) O(n)
  • Space complexity (Alan Karmaşıklığı) :
    • Serialize (Space) O(n)
    • Deserialize (Space) O(n)