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.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.
Yorumlar
Yorum Gönder