CP #12 : Serialize Deserialize Binary Tree Problemi

 Problem surada.

Cozum

Problemde bizden bir sekilde verilen bir binary tree''yi string seklinde serialize etmemiz isteniyor. Ayni sekilde bu stringi daha sonra deserialize edip binary tree'yi tekrar olusturmamiz gerek.

Naive bir baslangic olarak, pre-order traversal ile serialize edelim. Null tipleri icin de ozle bir karakter olarak "^" kullanacagim. 

def serialize(self, root):

    # eger TreeNode, None ise, bunu ozel bir karakterle temsil edebiliriz

    if not root:

        return "^"

    arr = [str(root.val), self.serialize(root.left), self.serialize(root.right)]

    return ",".join(arr)

seklinde recursive sekilde verilen binary tree'yi serialize edebiliriz. Bir ornek:

Zaten pre-order traversal yaptigimiz icin once root.val sonra left, sonra da  right branchlari alip stringe ceviriyoruz. Bunun sonucunda

1,2,^,^,3,4,^,^,5,^,^

seklinde bir string elde ediyoruz. Simdiki gorevimiz de bunu parse etmek. 

Diyelim ki parse etmeye 1'den basladik. Root.val olarak 1'i atadik. Daha sonra sol branctan devam etmemiz gerekiyor. Ve sol branchin ne kadar gidecegini bilmiyoruz. Sol branch bittikten sonra, sag brancha gecmemiz gerekiyor. Aslinda bu da gosteriyor ki, sol branch bittigi zaman, sagdan devam etmek icin hangi indexte oldugumuzu bilmemiz gerekiyor. Dolayisi ile yazacagimiz recursive deserialization metodu, bize hem olusturulan TreeNode'u dondurmeli, hem de devam etmek icin gerekli olan karakter indexini dondurmeli. Bu sayede sol branch bittikten sonra sag branchtan (yani ornekte 3'ten) devam edebiliriz.  

Bunun icin de verilen deserialization metoduna ek olarak, ayni zamanda baslangic karakter indexini de arguman olarak alan yardimci bir metot yaziyorum.

def de_rec(self, arr, start):

    # eger mevcut karakter ^ ise, bu bir None degeridir.

    if arr[start] == "^":

        return None

    # mevcut karakteri (arr[start) oku ve bir TreeNode olustur

    node = TreeNode(int(arr[start]))

    # simdi sol branchtan basliyoruz. Burada start degerini 1 artirdik

    # cunku root.val degerini yukarda okuduk. Sol branch bir sonraki 

    # karakterden devam ediyor

    node.left, continue_index = self.de_rec(arr, start+1)

    # recursive olarak sol taraf bittikten sonra, sagdan devm edecegiz

    # ayni zamanda sag branch da bittigi zamanki karakter index degeri bize lazim

    # cunku de_rec metodu bunu geri dondurmeli ki, bir sonraki adim 

    # devam edebilsin

    node.right, continue_index_2 = self.de_rec(arr, continue_index)

    return (node, continue_index_2)

def deserialize(self, data):

    # verilen string datayi split ederek karakterlere ayiriyoruz

    # ve ilk karakterden parse etmeye basliyoruz 

    node, index = self.de_rec(data.split(","), start=0)

    return node

 

Analiz

Serializasyonda turm binary tree'yi bir kere traverse ettik. Bu da O(n) demek oluyor. Memory olarak da her bir node degerini string icerisinde barindirdigimiz icin yine lineer olarak O(n) bir yapi elde etmis olduk. Deserializasyon da benzer sekilde. Verilen stringi one-pass ile parse ettik ve binary tree'yi olsutrduk. Yani O(n) runtime ve O(n) hafiza kompleksitesine sahip olduk.

Gorusmek uzere. 

Stay hungry, stay foolish, stay healthy :)