LeetCode 117: Her Düğümde Bir Sonraki Sağ İşaretçiyi Doldurma II
Bu makalede, LeetCode’daki 117. problem olan “Her Düğümde Bir Sonraki Sağ İşaretçiyi Doldurma II” problemini detaylı olarak inceleyeceğiz. Problem, bir ikili ağaçtaki her düğümün “next” işaretçisini, aynı seviyedeki bir sonraki düğüme işaret edecek şekilde ayarlamamızı istiyor. Fakat bu problemde, ağacın mükemmel bir ikili ağaç olması gerekmiyor; yani her düğümün iki çocuğu olmak zorunda değil.
Öncelikle, problemin özünü daha iyi anlamak için bir örnek verelim. Aşağıdaki gibi bir ağaç yapısı düşünelim:
1
/ \
2 3
/ \ \
4 5 7
Bu ağacın düzgün bir şekilde “next” işaretçileri ile doldurulmuş hali şöyle olmalıdır:
1 ---> NULL
/ \
2 --> 3 ---> NULL
/ \ \
4 --> 5 --> 7 ---> NULL
Bu problemi çözmenin birkaç farklı yolu vardır. En yaygın yaklaşımlar katmanlı tarama (level order traversal) kullanmaktır. Bu yöntemde, ağacı seviye seviye gezer ve her seviyedeki düğümleri bir kuyruk (queue) yapısı kullanarak işleriz. Aşağıda bu yöntemi gösteren bir Python kod örneği bulunmaktadır:
class Node:
def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
self.val = val
self.left = left
self.right = right
self.next = next
def connect(root: 'Node') -> 'Node':
if not root:
return root
queue = [root]
while queue:
level_size = len(queue)
prev = None
for i in range(level_size):
curr = queue.pop(0)
if prev:
prev.next = curr
prev = curr
if curr.left:
queue.append(curr.left)
if curr.right:
queue.append(curr.right)
prev.next = None #Seviyenin son düğümünün next'ini NULL yapar.
return root
Bu kod, öncelikle bir kuyruk kullanarak ağacı seviye seviye işler. Her seviye için, önceki düğümün next işaretçisi, geçerli düğüme ayarlanır. Bu şekilde, her seviyedeki düğümler birbirine bağlanır. Sonrasında, her seviyenin son düğümünün next işaretçisi None olarak ayarlanır.
Başka bir yöntem ise yinelemeli bir yaklaşım kullanmaktır. Bu yöntem, daha az bellek kullanabilir ancak daha karmaşık olabilir. İki yöntem arasında zaman ve bellek karmaşıklıkları da farklılık gösterir. Seçilecek yöntem problemin ölçeğine ve gereksinimlere göre değişebilir. Daha detaylı bilgi için buraya bakabilirsiniz.
Bu problem, ağaç veri yapılarının ve algoritmalarının anlaşılması açısından oldukça önemlidir. Çözümde kullanılan yöntemler, birçok diğer ağaç tabanlı problemde de kullanılabilir. Daha fazla algoritma ve veri yapısı örneği için kendi web sitemi Fatih Soysal ziyaret edebilirsiniz.
#Etiketler
LeetCode, 117, İkili Ağaç, Ağaç Algoritmaları, Veri Yapısı, Programlama, Algoritma, Çözüm, Katmanlı Tarama, Kuyruk, İteratif, Rekürsif