CP #30: Maximum Width of Binary Tree Problemi
Problem surada.
Cozum
Ilk aklima gelen cozum sekli, BFS ile tree'yi traverse edip, her bir levelin width'ine bakmak. Ama aralardaki None'lari da hesaba katmamiz gerektigi icin, kucuk bir modifiye ile, bir None node icin, iki tane None child eklmem lazim queue'ya. Bu sekilde None olan parent node'larin cocuklarini da kaybetmemis olacagiz.
Ama bir tehlike var. Eger None olan node'lar icin 2 tane de None cocuk eklersek, bu dongu hicbir zaman bitmez. Queue sonsuza kadar uzar. Bunun onune gecmek icin eger bir level'deki node'larin tamami None ise, donguyu orada bitirmemiz lazim. Konusarak anlatmasi zor, koda gecelim:
from collections import deque
def widthOfBinaryTree(self, root: TreeNode) -> int:
q = deque([root])
max_width = 0
# que'de eleman oldugu surece
while q:
lenq = len(q)
# mevcut leveldeki tum elemanlari itere et
# child node'lara bak
level = []
for _ in range(lenq):
cur = q.popleft()
# eger bu node None ise
# gelecek levelde 2 tane None child'i olmasi gerekiyor
# cunku problem taniminda width icin aralardaki None'lari da sayak gerek
if not cur:
q.append(None)
q.append(None)
level.append(None)
level.append(None)
continue
# sol child var ise
if cur.left:
level.append(cur.left.val)
q.append(cur.left)
else:
level.append(None)
q.append(None)
# sag child var ise
if cur.right:
level.append(cur.right.val)
q.append(cur.right)
else:
level.append(None)
q.append(None)
# simdi level'deki tum node'lar None ise
# demek ko sona geldik.
# hic max_width hesaplama, oncekini dondur
if not any(level):
return max_width
else:
# sikinti su ki, iki tane None olmayan node var ise
# bunlarin arasindaki mesafe kadar max_width degeri olacaktir
non_null_indexes = [i for i in range(len(level)) if level[i] is not None]
cur_max = max(non_null_indexes) - min(non_null_indexes) + 1
max_width = max(max_width, cur_max)
return max_width
Analiz
Evet bu cozum calisiyor. Birkac edge case haric! Yine de biz bir runtime compl.'ye bakalim. BFS yapiyoruz, her bir node bir kere ziyaret ediliyor. Buradan bir O(n) geliyor. Ancak her bir node ziyaretinde, max_width hesaplamasi yapiyoruz. Burada level icerisindeki None olmayan elemanlarin indexlerini bulmak icin bir kere donuyoruz, (O(n)). Daha sonra max ve min degerlerini aliyoruz ki bu da O(n). Ama bu islem arka arkaya oldugu icin toplamda max_width hesaplama islemi O(n)'e tekabul ediyor. BFS'le birlikte O(n^2) bir cozum elde etmisiz diyebiliriz.
Evet bu cozum calisiyor. Birkac edge case haric! Yine de biz bir runtime compl.'ye bakalim. BFS yapiyoruz, her bir node bir kere ziyaret ediliyor. Buradan bir O(n) geliyor. Ancak her bir node ziyaretinde, max_width hesaplamasi yapiyoruz. Burada level icerisindeki None olmayan elemanlarin indexlerini bulmak icin bir kere donuyoruz, (O(n)). Daha sonra max ve min degerlerini aliyoruz ki bu da O(n). Ama bu islem arka arkaya oldugu icin toplamda max_width hesaplama islemi O(n)'e tekabul ediyor. BFS'le birlikte O(n^2) bir cozum elde etmisiz diyebiliriz.
Zaten leetcode'da submit edince timeout oluyor :D
Bu cozumu nasil iyilestirebiliriz?
Oncelikle None degerleri tekrar queue'ye eklememize gerek var mi gercekten? Burada daha akilli bir yontem olabilir mi? Bize aslinda gereken level icerisindeki mix-max index degerleri. Bunu hesaplamak icin soyle bir herustic var(mis):
Burada her bir node'un indexini goruyoruz. Bu index degerlerinde soyle bir pattern var:
left_index = 2 * parent_index + 1
right_index = 2 * parent_index + 2
Yine BFS ile tree'yi traverse edip, her bir leveldeki min max indexleri O(1) ile bulabiliriz. Bu durumda toplamda O(n) bir cozum elde etmis oluruz.
def widthOfBinaryTree(self, root: TreeNode) -> int:
max_width = 0
# her bir node'u index degeri ile beraber tutarsak
# queue'da, kolaylik olur
q = deque([(root, 0)])
while q:
lenq = len(q)
# queue'den daha pop etmeden
# en bastaki elemanin indexine bakalim
min_index = q[0][1]
# ayni sekilde ensondaki elemanin indexine bakiyoruz
max_index = q[-1][1]
# bu yaklasimda sadece None olmayanlari queue'ya dahil ettigimiz icin
# yukaridaki yontem ise yaramaktadir
for _ in range(lenq):
cur, index = q.popleft()
if cur.left:
# soldaki child node'un indexi 2*parent+1 olacaktir
q.append((cur.left, 2 * index +1))
if cur.right:
# sagdaki child node'un indexi de 2*parent + 2 olacak
q.append((cur.right, 2 * index + 2))
return max_width
Analiz 2
BFS ile tum tree'yi traverse ettigimiz icin dis donguden O(n) geliyor. Iceride ise bu sefer bisey yok. Max-width hesaplamasi sadece bir lookup ve O(1) seklinde oluyor. Toplamda O(n) bir cozum. Leetcode'da da pass ediyor ve python gonerilerinin %67'sinden daha hizli. Daha performansli olan cozumler de ayni yaklasimi takip ediyor asagi yukari ama daha fazla iste list comprahension gibi native dil ozelliklerini kullanmislar.
BFS ile tum tree'yi traverse ettigimiz icin dis donguden O(n) geliyor. Iceride ise bu sefer bisey yok. Max-width hesaplamasi sadece bir lookup ve O(1) seklinde oluyor. Toplamda O(n) bir cozum. Leetcode'da da pass ediyor ve python gonerilerinin %67'sinden daha hizli. Daha performansli olan cozumler de ayni yaklasimi takip ediyor asagi yukari ama daha fazla iste list comprahension gibi native dil ozelliklerini kullanmislar.
Diger bir problemde gorusmek uzere.
Stay healthy :)
Yorumlar
Yorum Gönder