CP #47: Binary Tree Problemleri 3
12. Reconstruct A Binary Tree From Traversal Data
Pre-order ve pre-order node dizilimleri iki liste halinde verilmis olan bir binary tree'yi tekrar olusturunuz. (leetcode)
Cozum
Elimizde neler var once ona bir bakalim.
1. Preorder traversal'de ilk eleman her zaman tree'nin root node'u olacaktir. Bu durumda root node'u biliyoruz.
2. Inorder traversal icerisinde, root node'a kadar olan kisim left subtree'dir. Root node'dan sonraki kisim ise right subtree'dir.
3. Inorder traversal bilgisi kullanarak, left subtree'de kac tane node oldugunu hesaplayabiliriz. Yapmamiz gereken, root'un indexini bulmek. Left subtree'de kac tane node oldugunu bulur isek, preorder traversalda root'tan baslayarak o kadar node gidersek, sag subtree'ye ulasmis oluruz. Ornekte yesil kutucuk olarak gorulebilir.
Bu ilk uc adimi izledigimizde, verilen bir binary tree icin root, left subtree icin inorder ve preorder traversal degerleri ve de right subtree icin de inorder ve de preorder traversal degerlerini elde edebiliyoruz. O zaman, recursive olarak left subtree icin de ayni adimlari izleyebiliriz. Benzer sekilde right subtree icin de benzer adimlari izleyerek tum tree'yi bu sekilde olusturabiliriz.
def binary_tree_from_preorder_inorder(preorder, inorder):
# recursive olarak root node olusturacak metodumuz
# arguman olarak preorder ve inonrder traversal degerlerinini baslangic ve bitis
# indexlerini aliyor.
# en basta baslangic degerleri 0 ve de bitis degerleri array length olacak
def build_tree(pre_start, pre_end, in_start, in_end):
# deger disina cikiyorsak, leaf node'a ulasmisiz demektir
if pre_start >= pre_end or in_start >= in_end:
return None
# root node zaten belli, preorder'in ilk elemani
# ama inorder traversal icerisinde de root'un indexini bulacagiz ki
# sol subtree'de kac eleman oldugunu bulabilelim
root_index_in_inorder = inorder.index(preorder[pre_start])
# bu durumda sol subtree eleman sayisi da :
left_size = root_index_in_inorder - in_start
# simdi recursive noktaya geldik
return TreeNode(
val = preorder[pre_start],
left = build(
# left subtree, pre_orderin ilk elemanindan sonra basliyor
# cunku ilk eleman root node
# yukaridaki ornekte yesil kutucuk left subtree'yi gosteriyor
pre_start = pre_start + 1,
# sol subtree'de kac eleman oldugunu biliyoruz, o zaman bitis
# indexi, baslangic + left_size olacaktir
pre_end = pre_start + 1 + left_size,
# yukaridaki diagramda inorder icin left subtree
# baslangic ve bitis indexleri goruluyor
in_start = in_start,
in_end = root_index_in_inorder),
right = build(
# yesil kutucuk sol subtee'yi gosteriyor ise, ondan geri kalan kisim
# right subtree olacaktir. right subtree'nin baslangic noktasi,
# sol subtree'nin bittigi index degeri olur.
pre_start = pre_start + 1 + left_size,
pre_end = pre_end,
in_start = root_index_in_inorder + 1,
in_end = in_end)
)
# recursion'a treenin tamamindan basliyoruz
return build(
pre_start = 0,
pre_end = len(preorder),
in_start = 0,
in_end = len(inorder)
)
Bakacak olursak, her bir node'u bir kere ziyaret ederek olusturuyoruz. Buradan bir O(n) maliyeti geliyor. Her bir adimda ise, tek komplikasyon, inorder icerisinde root node'un indexini bulmakta. Burada da bir O(n) maliyet var. Ve bu her bir adimda gerceklestigi icin toplamda O(n^2) bir maliyet ortaya cikiyor. Bunu tabi ki optimize edebiliriz. Bize gerekli olan her bir inorder elemani icin, kendisine ait index degeri. Bu sayede bir lookup ile root'tan indexi O(1) ile elde edebiliriz.
En basta:
inorder_cache = {}
for i in range(len(inorder)):
inorder_cache[inorder[i]] = i
seklinde bir lookup table yaparsak, her bir elemanin indexini bulmak O(1) ile mumkun olacaktir.
Iceride de bu sefer python'un index metodu yerine:
root_index_in_inorder = inorder_cache[preorder[pre_start]]
seklinde lookup gerceklestirabiliriz.
Bu sayede toplamda O(n) time compl. sahip bir cozum elde etmis oluyoruz. Space maliyeti ise, recursiondan kaynakli system call stack'indan gelen O(h) ve de lookup table'dan gelen O(n) ile birlikte toplamda O(n+h) olarak karsimiza cikiyor.
13. Construct Binary Tree from Inorder and Postorder Traversal
In-order ve post-order node dizilimleri iki liste halinde verilmis olan bir binary tree'yi tekrar olusturunuz. (leetcode).
Cozum
Yine yukaridaki cozum mantigi ile benzer sekilde, recursive olarak sol ve sag subree'leri olusturabiliriz. Burada degisen sey root'un konumu (artik postorder'in son elemani) ve de sol-sag sub-tree'lerin baslangic ve bitis indexleri olacaktir. Bunlari dikkatli bir sekilde olusturmamiz gerekiyor.
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
# yine inoder icerisinde root node'u bulmak icin lookup table olusturuyoruz
inorder_cache = {}
for i in range(len(inorder)):
inorder_cache[inorder[i]] = i
def build(in_start, in_end, post_start, post_end):
if in_start >= in_end or post_start >= post_end:
return None
# root pozisyonu bu sefer postorder'in son elemani
root_index_in_inorder = inorder_cache[postorder[post_end - 1]]
left_size = root_index_in_inorder - in_start
return TreeNode(
val = postorder[post_end - 1],
left = build(
in_start = in_start,
in_end = root_index_in_inorder,
post_start = post_start,
post_end = post_start + left_size),
right = build(
in_start = root_index_in_inorder + 1,
in_end = in_end,
post_start = post_start + left_size,
post_end = post_end-1)
)
return build(0, len(inorder), 0, len(postorder))
Time compl. yine O(n) ve de space compl. lookup table + system call stack O(n+h) olarak goze carpiyor.
14. Construct Max-Tree
Birbirinden farkli integer sayilar iceren bir A arrayi olsun. Bu arrayin maksimum elemaninin indexi ise m olsun. A uzerinde recursive olarak binary tree olusturunuz. Olusturulacak tree'de root, A uzerindeki maks eleman olmalidir. Sol subtree icin A[0, m+1] ve sag subtree icin A[m+1, n-1] arraylari kullanilarak ayni mantik ile maks eleman root olacak sekilde tree'yi olusturunuz.
(leetcode)
(leetcode)
Cozum
Soru biraz uzun ve karmasik gorunse de, onceki iki probleme cok yakin. Verilen bir A arrayi icin, array icerisindeki maks elemani ve de indexini bulduktan sonra, sol ve sag subtree'leri yine recursive olarak olsutrabiliriz.
def constructMaximumBinaryTree(A):
def build(start, end):
# leaf node kontrolu
if end <= start:
return None
# verilen araliktaki maks elemanin indexi, root index olacaktir
root_index = A.index(max(A[start:end]))
return TreeNode(
val = A[root_index],
left = build(start, root_index),
right = build(root_index + 1, end))
return build(0, len(A))
Time compl. bakacak olursak, O(n^2) olduguu goruyoruz. Problem root_index'te gerceklesiyor. A[start:end] uzerinde max'i bulmak O(n) zaten. Sonrasinda da index buluyoruz ki bu da O(n). Gerci bu iki islem arka arkaya oldugu icin O(2n) => O(n) oluyor ancak yine de toplam time compl. bu sekilde O(n^2)'ye cikmis oluyor. Onceki cozumlerdeki gibi bir lookup table yaparsak, A.index metodundan kurtuluruz ancak max islemi yine orada duruyor olacaktir.
Bu soruyu monotonic stack yontemi ile O(n) sekilde cozmek mumkunmus. Bir sonraki postta bu konuya deginiriz.
Gorusmek uzere.
Yorumlar
Yorum Gönder