TreeNode Sınıfı ve Seviye Sıralı BFS
Dizilerden ikili ağaçlar oluşturun, seviyeleri ayrı ayrı yazdırmak için deque ile BFS uygulayın ve BFS kullanarak maksimum derinliği bulun.
TreeNode Sınıfı ve Seviye Sıralı BFS, CoddyKit'te ücretsiz bir DSA Interview Prep dersidir. Bu, 4 dersinin 1. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, DSA Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. DSA Interview Prep kursu toplamda 4 dersten oluşur.
TreeNode Sınıfının Temelleri
İkili ağaç, her düğümün sol ve sağ adı verilen en fazla iki çocuğa sahip olduğu hiyerarşik bir veri yapısıdır. Python'da bir düğümü basit bir sınıfla modelleriz: class TreeNode: def __init__(self, val=0, left=None, right=None). Mülakatlardaki her ağaç problemi bu tanımla başlar — bu tanımı neredeyse her LeetCode ağaç probleminin kalıp kodunda görürsünüz.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Build a small tree manually:
# 1
# / \
# 2 3
# / \
# 4 5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(root.val, root.left.val, root.right.val)Dizilerden Ağaç Oluşturma
Mülakat problemleri size genellikle seviye sıralı dizi olarak gösterilen bir ağaç verir; eksik düğümleri None belirtir. i indisi verildiğinde sol çocuk 2i+1, sağ çocuk ise 2i+2 konumundadır. Bu dizinin serileştirmesini geri alıp birbirine bağlı TreeNodes nesnelerine dönüştüren bir yardımcı yazmak, alıştırma oturumlarında zaman kazandıran değerli bir araçtır.
from collections import deque
def build_tree(arr):
if not arr or arr[0] is None:
return None
root = TreeNode(arr[0])
q = deque([root])
i = 1
while q and i < len(arr):
node = q.popleft()
if i < len(arr) and arr[i] is not None:
node.left = TreeNode(arr[i])
q.append(node.left)
i += 1
if i < len(arr) and arr[i] is not None:
node.right = TreeNode(arr[i])
q.append(node.right)
i += 1
return root
root = build_tree([1, 2, 3, 4, 5, None, 6])
print(root.val, root.left.val, root.right.val)BFS Nedir ve Neden Kuyruk Kullanılır?
Genişlik Öncelikli Arama (BFS), d derinliğindeki tüm düğümleri d+1 derinliğindeki herhangi bir düğümü ziyaret etmeden önce ziyaret eder. Seviyeleri tek tek işleyen bu gezinme, bize tam olarak bir kuyruğun (FIFO) sağladığı şeyi verir: kök düğümü kuyruğa ekler, ardından düğümleri birer birer işler ve ilerlerken her düğümün çocuklarını kuyruğa ekleriz. Python'un collections.deque yapısı O(1) zamanında appendleft ve popleft işlemleri sunduğu için normal bir listeye göre doğru seçimdir.
from collections import deque
def bfs_print(root):
if not root:
return
q = deque([root])
while q:
node = q.popleft()
print(node.val, end=' ')
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
bfs_print(root) # 1 2 3 4Seviye Sıralı BFS: Seviyelere Göre Gruplama
Standart BFS çeşidi, her yinelemenin başındaki kuyruk boyutunu kaydederek düğümleri seviyelere ayırır. Tam olarak bu sayıdaki düğümü işleyin, değerlerini toplayın, ardından bir sonraki seviyeye geçin. Böylece, ikili ağaçta seviye sıralı gezinme, zikzaklı gezinme ve sağdan görünüm gibi problemlerde çok sık kullanılan bir liste listesi çıktı biçimi elde edilir.
from collections import deque
def level_order(root):
if not root:
return []
result = []
q = deque([root])
while q:
level_size = len(q)
level = []
for _ in range(level_size):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(level)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(level_order(root)) # [[1], [2, 3], [4]]BFS ile Maksimum Derinlik
Bir ikili ağacın maksimum derinliği, BFS gezinmesindeki seviye sayısına eşittir. Bir seviye döngüsünü kaç kez tamamladığınızı saymanız yeterlidir. Böylece O(n) zaman ve w'nin ağacın maksimum genişliği olduğu O(w) alan kullanan bir çözüm elde edilir. Dengeli bir ağaçta w, O(n/2) değerindedir; dolayısıyla en kötü durum alan karmaşıklığı O(n)'dir.
from collections import deque
def max_depth_bfs(root):
if not root:
return 0
depth = 0
q = deque([root])
while q:
depth += 1
for _ in range(len(q)):
node = q.popleft()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return depth
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(max_depth_bfs(root)) # 3İkili Ağacın Sağdan Görünümü
Sağdan görünüm, ağaca sağdan baktığınızda görünen son düğümü, yani BFS gezinmesindeki her seviyenin son öğesini döndürür. Bu, seviye sıralı BFS'nin doğrudan bir uygulamasıdır: her seviye döngüsündeki son düğümü toplayın. Zaman karmaşıklığı O(n), kuyruk için alan karmaşıklığı O(w)'dir.
from collections import deque
def right_side_view(root):
if not root:
return []
result = []
q = deque([root])
while q:
level_size = len(q)
for i in range(level_size):
node = q.popleft()
if i == level_size - 1:
result.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(5)
print(right_side_view(root)) # [1, 3, 5]Zikzak Seviye Sıralı Dolaşım
Zikzak dolaşmada tek sayılı seviyeler soldan sağa, çift sayılı seviyeler sağdan sola toplanır. En temiz uygulama, BFS kuyruğunu değiştirmeden bırakır ve sonuç listesine eklemeden önce dönüşümlü seviye listelerini ters çevirir. Yönü, her seviyede değişen bir boole bayrağıyla takip edin. Bu yöntem, iç döngüde çift uçlu kuyruk karmaşıklığını önler.
from collections import deque
def zigzag_level_order(root):
if not root:
return []
result = []
q = deque([root])
left_to_right = True
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(level if left_to_right else level[::-1])
left_to_right = not left_to_right
return result
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(zigzag_level_order(root))BFS Bellek Karmaşıklığı Analizi
BFS, w ağacın maksimum genişliği olmak üzere O(w) bellek kullanır. Tam ikili ağaçta n düğüm varsa son seviyede (n+1)/2 düğüm bulunur; bu nedenle BFS aynı anda kuyrukta n/2 düğüme kadar tutabilir. Bu durum, geniş ve dengeli ağaçlarda BFS'yi bellek açısından DFS'den (O(h)) daha kötü, DFS çağrı yığını derinliğinin n'ye eşit olduğu derin ve çarpık ağaçlarda ise daha iyi hâle getirir.
# Space comparison: BFS vs DFS on a complete binary tree
# n=15 nodes, height=4
# BFS max queue size = 8 (last level)
# DFS max call stack = 4 (height)
# For a skewed tree (like a linked list):
# n=1000 nodes
# BFS max queue size = 1 (always 1 node per level)
# DFS max call stack = 1000 (recursion depth -> stack overflow!)
from collections import deque
def skewed_tree(n):
root = TreeNode(1)
cur = root
for i in range(2, n+1):
cur.right = TreeNode(i)
cur = cur.right
return root
root = skewed_tree(10)
print('BFS on skewed tree is safe')İkili Ağaçta Seviyelerin Ortalaması
Her seviyedeki ortalama değeri hesaplamak, BFS'nin doğrudan bir başka uygulamasıdır. Bir seviyedeki tüm değerleri toplayın, düğüm sayısına bölün ve sonuç listesine append edin. Bu problem, seviye döngüsü içinde aritmetik işlemler yapabildiğinizi sınar. Python 3'te her zaman float bölmesi (/ işleci) kullanın ve boş ağaç durumunu başlangıçta ele alın.
from collections import deque
def average_of_levels(root):
if not root:
return []
result = []
q = deque([root])
while q:
size = len(q)
total = 0
for _ in range(size):
node = q.popleft()
total += node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(total / size)
return result
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(average_of_levels(root)) # [3.0, 14.5, 11.0]BFS ile Minimum Derinlik
Minimum derinlik, kökten en yakın yaprak düğüme (çocuğu olmayan bir düğüme) olan uzaklıktır. BFS bunu en uygun şekilde bulur: seviye sıralı dolaşım sırasında karşılaşılan ilk yaprak düğümün minimum derinlikte olması garanti edilir. Bir yaprağa ulaşır ulaşmaz geçerli derinliği döndürün. En kötü durumda karmaşıklık O(n)'dir; ancak dengeli ağaçlarda çoğu zaman çok daha erken sonlanır.
from collections import deque
def min_depth(root):
if not root:
return 0
q = deque([(root, 1)])
while q:
node, depth = q.popleft()
# A leaf has no children
if not node.left and not node.right:
return depth
if node.left:
q.append((node.left, depth + 1))
if node.right:
q.append((node.right, depth + 1))
return 0
root = TreeNode(2)
root.left = TreeNode(3)
root.left.left = TreeNode(4)
root.right = TreeNode(5) # leaf at depth 2
print(min_depth(root)) # 2Seviye Sıralı Kardeş Düğümleri Bağlama
Sağdaki düğüme işaretçileri doldurma problemi, her düğümü aynı seviyedeki sağ komşusuna bağlamanızı ister. BFS ile bu işlem basittir: her seviye döngüsünün içinde, son düğüm dışındaki tüm düğümler için node.next = q[0] ayarlayın. Bu, BFS'nin çözümü açıkça ortaya koyduğu; DFS'nin ise alt ağaçlar arasındaki işaretçileri dikkatle takip etmeyi gerektirdiği klasik bir örnektir.
from collections import deque
class Node:
def __init__(self, val=0, left=None, right=None, next=None):
self.val = val
self.left = left
self.right = right
self.next = next
def connect(root):
if not root:
return root
q = deque([root])
while q:
size = len(q)
for i in range(size):
node = q.popleft()
if i < size - 1:
node.next = q[0]
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return root
print('BFS connect: O(n) time, O(w) space')Kısa Kontrol
Bu dersteki Veri Yapıları ve Algoritmalar — Kodlama Mülakatına Hazırlık kavramlarını anlayıp anlamadığınızı test edin.
Ders Özeti
Bu derste şunları öğrendiniz: TreeNode sınıf tanımı ve dizilerden ağaç oluşturma, düğümleri gruplamak için seviye boyutu tekniğini kullanan çift uçlu kuyrukla seviye sıralı BFS ve maksimum derinlik, minimum derinlik, sağdan görünüm, zikzak dolaşma ve seviye ortalamaları gibi uygulamalar. Sırada özyinelemeli DFS dolaşım sıralarını inceleyeceğiz.
Sıkça Sorulan Sorular
“TreeNode Sınıfı ve Seviye Sıralı BFS” dersi ücretsiz mi?
Evet — “TreeNode Sınıfı ve Seviye Sıralı BFS” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve DSA Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. DSA Interview Prep kursu toplamda 4 dersten oluşur.
“TreeNode Sınıfı ve Seviye Sıralı BFS” dersinde ne öğreneceğim?
Dizilerden ikili ağaçlar oluşturun, seviyeleri ayrı ayrı yazdırmak için deque ile BFS uygulayın ve BFS kullanarak maksimum derinliği bulun. DSA Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
DSA Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te DSA Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 1. dersidir.
“TreeNode Sınıfı ve Seviye Sıralı BFS” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu DSA Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her DSA Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- TreeNode Sınıfı ve Seviye Sıralı BFS
- Sıralı, Ön Sıralı ve Son Sıralı DFS
- Çap, Yükseklik ve Dengeli Ağaçlar
- Yol Toplamı ve En Düşük Ortak Ata