Sıralı, Ön Sıralı ve Son Sıralı DFS
Üç DFS dolaşımının tümünü özyinelemeli olarak ve açık bir yığınla yinelemeli biçimde uygulayın; her sıralamanın ne zaman yararlı olduğunu açıklayın.
Sıralı, Ön Sıralı ve Son Sıralı DFS, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 2. 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, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.
Üç DFS Dolaşım Sırası
İkili ağaçta DFS, kökün çocuklarına göre ne zaman işlendiğine bağlı olarak düğümleri üç sıradan biriyle ziyaret eder. Ön sıralı: kök → sol → sağ. Ara sıralı: sol → kök → sağ. Son sıralı: sol → sağ → kök. Adlar, kökün dizide nereye yerleştirildiğini belirtir. Farklı problemler farklı sıralar gerektirdiği için üçünü de anlamak çok önemlidir.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Build: 1 -> left=2(left=4,right=5), right=3
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# pre: 1 2 4 5 3
# in: 4 2 5 1 3
# post: 4 5 2 3 1
print('Tree built successfully')Özyinelemeli Ön Sıralı Dolaşım
Ön sıralı dolaşımda geçerli düğüm, alt ağaçlarından önce işlenir. Bu sıra, ağacın doğal olarak yukarıdan aşağıya okunmasını yansıtır ve ağaç kopyalama, serileştirme ve önek ifadelerinin değerlendirilmesinde kullanılır. Özyinelemeli uygulama son derece kısadır; ancak yüksekliği h olan ağaç için O(h) derinliğinde bir çağrı yığını oluşturur.
def preorder(root):
if not root:
return []
return [root.val] + preorder(root.left) + preorder(root.right)
# More memory-efficient with an accumulator:
def preorder_v2(root, result=None):
if result is None:
result = []
if not root:
return result
result.append(root.val) # PROCESS ROOT FIRST
preorder_v2(root.left, result)
preorder_v2(root.right, result)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(preorder_v2(root)) # [1, 2, 4, 5, 3]Özyinelemeli Ara Sıralı Dolaşım
Ara sıralı dolaşım, önce sol alt ağacı, ardından kökü, sonra da sağ alt ağacı ziyaret eder. Bir İkili Arama Ağacı için ara sıralı dolaşım her zaman sıralı bir dizi üretir; bu özellik BST doğrulama, k'ıncı en küçük öğe ve BST'den sıralı dizi oluşturma gibi problemlerde kullanılır. BST problemleri için bilinmesi gereken en önemli dolaşım budur.
def inorder(root, result=None):
if result is None:
result = []
if not root:
return result
inorder(root.left, result) # left subtree first
result.append(root.val) # PROCESS ROOT MIDDLE
inorder(root.right, result) # right subtree last
return result
# For a BST, inorder gives sorted output:
from collections import deque
def make_bst():
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
return root
bst = make_bst()
print(inorder(bst)) # [1, 2, 3, 4, 6] - sorted!Özyinelemeli Son Sıralı Dolaşım
Son sıralı dolaşım, geçerli düğümden önce her iki çocuğu da işler. Bu aşağıdan yukarıya sıra, üst düğümün hesaplaması çocuklarının sonuçlarına bağlı olduğunda doğaldır; örneğin alt ağaç boyutlarını hesaplarken, ağacı silerken veya bir ifade ağacını değerlendirirken. Bilgiyi yukarıya aktaran ağaç problemlerinin çoğu örtük son sıralı mantığı kullanır.
def postorder(root, result=None):
if result is None:
result = []
if not root:
return result
postorder(root.left, result) # left subtree
postorder(root.right, result) # right subtree
result.append(root.val) # PROCESS ROOT LAST
return result
# Use case: delete a tree (children before parent)
def delete_tree(root):
if not root:
return
delete_tree(root.left)
delete_tree(root.right)
print(f'Deleting node {root.val}') # safe: children gone
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(postorder(root)) # [4, 2, 3, 1]Yığınla Yinelemeli Ön Sıralı Dolaşım
Özyineleme derinliği sınırlarını aşmamak için DFS'yi açık bir yığın kullanarak yinelemeli biçimde uygulayın. Ön sıralı dolaşım için kökü yığına ekleyin; ardından her yinelemede bir düğümü pop edin, kaydedin ve önce sağ çocuğunu, sonra sol çocuğunu yığına ekleyin (solun önce işlenmesi için sağ önce eklenir). Bu, çağrı yığınının LIFO davranışını taklit eder ve Python'ın 1000 olan varsayılan özyineleme sınırının yetersiz kalacağı derin ağaçlarda başvurulan yöntemdir.
def preorder_iterative(root):
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val) # process now
if node.right: # push right FIRST
stack.append(node.right)
if node.left: # push left second (popped first)
stack.append(node.left)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(preorder_iterative(root)) # [1, 2, 4, 5, 3]Yığınla Yinelemeli Ara Sıralı Dolaşım
Yinelemeli ara sıralı dolaşım biraz daha karmaşıktır. Bir yığın ve curr işaretçisi kullanın: mümkün olduğu kadar sola ilerlerken her düğümü yığına ekleyin. Daha fazla sola ilerleyemediğinizde pop edin, düğümü kaydedin ve ardından sağa ilerleyin. Boş değere ulaşana kadar sola ekle, pop edip işle, sonra sağa ilerle biçimindeki bu kalıp, BST yineleyicisi problemlerinde görülen temel yinelemeli tekniklerden biridir.
def inorder_iterative(root):
result = []
stack = []
curr = root
while curr or stack:
# Go as far left as possible
while curr:
stack.append(curr)
curr = curr.left
# Pop and process
curr = stack.pop()
result.append(curr.val)
# Move to right subtree
curr = curr.right
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(inorder_iterative(root)) # [4, 2, 5, 1, 3]İki Yığınla Yinelemeli Son Sıralı Dolaşım
Yinelemeli son sıralı dolaşımın kullanışlı bir hilesi vardır: değiştirilmiş bir ön sıralı dolaşım (kök → sağ → sol) gerçekleştirin ve sonuçları ters sırada toplayın. Kökü yığına ekleyin, pop edip sonucun başına ekleyin, ardından solu ve sağı yığına ekleyin. Ters çevirme, kök-sağ-sol sırasını sol-sağ-kök sırasına dönüştürür; bu da tam olarak son sıralı dolaşımdır. Alternatif olarak, tek yığınla son ziyaret edilen düğümü takip etmek için bir prev işaretçisi kullanabilirsiniz.
from collections import deque
def postorder_iterative(root):
if not root:
return []
result = deque()
stack = [root]
while stack:
node = stack.pop()
result.appendleft(node.val) # prepend = reverse pre-order
if node.left:
stack.append(node.left) # push left first
if node.right:
stack.append(node.right) # push right second
return list(result)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(postorder_iterative(root)) # [4, 5, 2, 3, 1]Hangi Dolaşımı Ne Zaman Seçmeli
Doğru dolaşımı seçmek, mülakatlarda önemli bir göstergedir. Bir üst düğümü çocuklarından önce işlemeniz gerektiğinde ön sıralı dolaşımı kullanın (ağacı serileştirme, yapıyı kopyalama). Sıralı düzenden yararlanmak için BST'lerde ara sıralı dolaşımı kullanın. Her iki çocuğa bağlı değerleri hesaplarken son sıralı dolaşımı kullanın (height, çap, alt ağaç toplamı). En kısa yol ve seviyeleri gruplama problemlerinde BFS tercih edilir.
# Pattern summary:
# Pre-order -> top-down: parent info flows DOWN to children
# In-order -> BST sorted property, kth element, validate BST
# Post-order -> bottom-up: children info flows UP to parent
# BFS -> shortest path, level grouping, level averages
# Example: compute subtree sum (post-order because
# we need left + right sum before computing total)
def subtree_sum(root):
if not root:
return 0
left = subtree_sum(root.left)
right = subtree_sum(root.right)
return root.val + left + right # uses children FIRST
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(subtree_sum(root)) # 6Morris Dolaşımı: O(1) Bellekli Ara Sıralı Dolaşım
Morris dolaşımı, ağacı geçici olarak değiştirerek O(1) bellekle ara sıralı dolaşım gerçekleştirir. Sol alt ağacı olan her düğüm için ara sıralı öncülü (sol alt ağacın en sağındaki düğümü) bulun ve bu düğümün sağ işaretçisini geçerli düğüme geri bağlayın. Ziyaret ettikten sonra bağlantıyı eski hâline getirin. Bu ileri düzey teknik, mülakat yapan kişi ‘O(1) ek bellekle yapabilir misiniz?’ diye sorduğunda üst düzey mülakatlarda karşınıza çıkabilir.
def morris_inorder(root):
result = []
curr = root
while curr:
if not curr.left:
result.append(curr.val)
curr = curr.right
else:
# Find in-order predecessor
pred = curr.left
while pred.right and pred.right != curr:
pred = pred.right
if not pred.right:
# Make thread and move left
pred.right = curr
curr = curr.left
else:
# Remove thread, visit, move right
pred.right = None
result.append(curr.val)
curr = curr.right
return result
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
print(morris_inorder(root)) # [1, 2, 3, 4, 6]Dolaşımlardan Ağacı Yeniden Oluşturma
Ön sıralı ve ara sıralı diziler verildiğinde özgün ağacı yeniden oluşturabilirsiniz. Ön sıralı dizinin ilk öğesi her zaman köktür. Bu kökü ara sıralı dizide bulun; kökün solundaki her şey sol alt ağaca, sağındaki her şey sağ alt ağaca aittir. Bu işlemi alt dizilere özyinelemeli olarak uygulayın. Karma tabloyla dizin araması kullanıldığında zaman karmaşıklığı O(n) olur.
def build_from_preorder_inorder(preorder, inorder):
if not preorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
mid = inorder.index(root_val)
# left subtree: inorder[0:mid], preorder[1:mid+1]
root.left = build_from_preorder_inorder(
preorder[1:mid+1], inorder[:mid])
# right subtree: inorder[mid+1:], preorder[mid+1:]
root.right = build_from_preorder_inorder(
preorder[mid+1:], inorder[mid+1:])
return root
pre = [3, 9, 20, 15, 7]
ino = [9, 3, 15, 20, 7]
root = build_from_preorder_inorder(pre, ino)
print(root.val, root.left.val, root.right.val) # 3 9 20Dolaşım Zamanı ve Belleği Özeti
Üç DFS dolaşımının da zaman karmaşıklığı O(n)'dir; çünkü her düğüm tam olarak bir kez ziyaret edilir. Bellek karmaşıklığı, ağacın yüksekliği h olmak üzere O(h)'dir: dengeli ağaçlarda O(log n), çarpık ağaçlarda ise O(n) olur (çağrı yığını veya açık yığın nedeniyle). Yinelemeli uygulamalar Python'ın özyineleme sınırını aşar; ancak asimptotik olarak aynı belleği kullanır. Morris dolaşımı, ağacın sağ işaretçilerini yeniden kullanarak benzersiz biçimde O(1) bellek sağlar.
# Complexity table:
# Traversal | Time | Space (recursion) | Space (iterative)
# -----------|------|-------------------|------------------
# Pre-order | O(n) | O(h) | O(h)
# In-order | O(n) | O(h) | O(h)
# Post-order | O(n) | O(h) | O(h)
# Morris | O(n) | O(1) | O(1)
# BFS | O(n) | O(w) | O(w)
# h = height, w = max width
# Balanced: h = log n, w = n/2
# Skewed: h = n, w = 1
print('O(n) time for all traversals')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: üç DFS dolaşım sırası (ön, ara, son) ve her birinin ne zaman seçileceği, açık yığın kullanan özyinelemeli ve yinelemeli uygulamalar ve Morris O(1) bellek tekniği. Sırada ikili ağaçların çapını, height değerini ve dengesini hesaplamayı inceleyeceğiz.
Sıkça Sorulan Sorular
“Sıralı, Ön Sıralı ve Son Sıralı DFS” dersi ücretsiz mi?
Evet — “Sıralı, Ön Sıralı ve Son Sıralı DFS” 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 Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.
“Sıralı, Ön Sıralı ve Son Sıralı DFS” dersinde ne öğreneceğim?
Üç DFS dolaşımının tümünü özyinelemeli olarak ve açık bir yığınla yinelemeli biçimde uygulayın; her sıralamanın ne zaman yararlı olduğunu açıklayın. Coding 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.
Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Coding 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 2. dersidir.
“Sıralı, Ön Sıralı ve Son Sıralı DFS” 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 Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Coding 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