CP #48: Binary Tree Problemleri 4

15. Reconstruct A Binary Tree From Preorder Traversal With Marks

Array seklinde preorder traversali verilmis olan binary tree'yi yeniden olusturunuz. Bos olan child node'lar None ile gosterilmis. 

Ornek: [1, None, 2] 

Root node:1 , left child: None, right child: 2 

Cozum

Preorder traversal verildiginden, root degerini bulmak icin ilk elemana bakmamiz yeterli. Daha sonraki elemanlar, sol subtree'ye ait olacaktir. Ama problem su ki, sol subtree'nin ne zaman bitip de sag subtree'nin basladigini bilemiyoruz. Ama recursive olarak gidersek, her bir adimda root'u biliyor olacagiz. Daha sonra da, array uzerinde nerede oldugumuzu belirten bir index kullanarak, yolumuzu bulabiliriz.

def reconstruct_preorder(preorder):

    # recursive olarak binary tree'yi olusturacak metodumuz

    # ayni zamanda verilen subtree'nin eleman sayisini da dondurmeli ki

    # ornegin sol subtree'nin nerede bittigini bilebilelim

    def rec(arr, start_index):

        # preorder'dan dolayi, root degeri arrayin ilk elemani olacaktir

        root_val = arr[0]

        

        # egere root None ise, bu bos bir node

        # recursion'a devam etmeye gerek yok

        if not root_val:

            # Tree node olarak None ve uzunluk olarak 1 donduruyoruz

            return (None, 1)

        # sol subtee ve uzunlugu

        # baslama noktasi index+1 cunku ilk eleman root

        # sol subtree root'tan hemen sonra basliyor

        left_node, left_size = rec(arr, start_index + 1)        

        

        # sol subtree'nin uzunlugunu bildigimiz icin

        # sag subtree nereden basliyor, artik biliyoruz 

        right_node, right_size = rec(arr, start_index + left_size + 1)

        # simdi bu arrayin temsil ettigi binary tree'yi dondurebiliriz

        # tabi uzunlugu ile beraber. uzunluk ise sol ve sag subtree uzunluklari toplami 

        # arti 1, cunku root node da var.

        return TreeNode(

            val=root_val,

            left=left_node,

            right=right_node), left_size + right_size + 1

    # recursive fonk. cagiralim ve sadece TreeNode kismini dondurelim.

    # rec fonksiyonu tuple donduruyor unutmayalim

    return rec(preorder, start_index=0)[0]

Baktigimiz zaman gayet O(n) time compl sahip bir cozum. Ekstra memory de kullanmiyoruz sadece system call stack'ten gelen O(h) space compl. var.

16. Compute The Leaves Of A Binary Tree

Root node'u verilen bir binary tree icin leaf node'lari soldan saga olacak sekilde bir array icerisinde dondurunuz. 

Ornek:

Bu binary tree icin [6, 7, 4, 0, 8] dondurulmesi gerekir.

Cozum

Soldan saga bir siralama istendigi icin, preorder gibi bir traversal yapabiliriz. Farkli olarak bu sefer root node uzerinde bir ilem yapmayacagiz. Surekli sola giden, leaf node bulunca bir arraya ekleyen ve de solda gidecek yer kalmayinca saga yonelen recursive bir DFS ile sonuca ulasabiliriz. 

def create_list_of_leaves(tree):

    # recursive DFS

    # eger leaf node'a rastlarsak, saklamak icin arr argumani aliyor

    def rec(node, arr):

        # leaf node mu?

        if not node.left and not node.right:

            arr.append(node)

            return

        # sola gidilebiliyorsa, gidiyoruz
        if node.left:   rec(node.left, arr)

        if node.right: rec(node.right, arr)

    arr = []

    rec(tree, arr)

    return arr

Bakacak olursak tree'deki her bir node'u bir kere ziyaret ediyoruz ve ekstra bir kompleksite yok. Bu durumda O(n) time compl. sahip bir cozum elde ettik demektir. Ekstra memory olarak leaf node'lari tutan bir arrayimiz var. Bir binary tree'de en fazla 2^h kadar leaf node olabilir. Ek olarak call stack'te O(h) kadar yer kapliyor recursive fonksiyonumuz. Toplamda, O(2^h + h) ekstra memory kullaniyoruz.

Bu kadar binary tree problemi simdilik yeterli. Gorusmek uzere.