Yol Toplamı ve En Düşük Ortak Ata
Genel bir ikili ağaçta özyinelemeli iniş kullanarak kökten yaprağa yol toplamı, tüm yolların toplamı ve en düşük ortak ata problemlerini çözün.
Yol Toplamı ve En Düşük Ortak Ata, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 4. 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.
Kökten Yaprağa Yol Toplamı
Yol toplamı problemi, herhangi bir kökten yaprağa yolun hedefe eşit bir toplam verip vermediğini sorar. Özyineleme boyunca kalan hedefi aşağı aktarın ve her düğümün değerini bu hedeften çıkarın. Bir yaprakta, kalanın yaprağın değerine eşit olup olmadığını kontrol edin. Bu yaklaşım, açıkça bir yol listesi tutmayı gerektirmez; bellek açısından verimli ve temizdir. Sınır durumu: boş bir ağacın yolu yoktur, bu nedenle hemen False döndürün.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def has_path_sum(root, target):
if not root:
return False
if not root.left and not root.right: # leaf
return root.val == target
remain = target - root.val
return (has_path_sum(root.left, remain) or
has_path_sum(root.right, remain))
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(2)
print(has_path_sum(root, 22)) # True: 5->4->11->2Tüm Kökten Yaprağa Yollar
Tüm yolları listelemek için güncel bir yol listesi tutun. Her özyinelemeli çağrıda geçerli düğümün değerini ekleyin, alt düğümlere özyinelemeli olarak ilerleyin, ardından dönüşte seçimi geri almak için pop uygulayın. Bir yaprakta, geçerli yolun anlık bir kopyasını (list(path)) kaydedin. Bu kalıp — seç, özyinele, seçimi geri al — ağaçlarda geri izlemenin temelidir.
def all_path_sums(root, target):
results = []
def dfs(node, path, remaining):
if not node:
return
path.append(node.val)
if not node.left and not node.right and remaining == node.val:
results.append(list(path)) # snapshot
else:
dfs(node.left, path, remaining - node.val)
dfs(node.right, path, remaining - node.val)
path.pop() # backtrack
dfs(root, [], target)
return results
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.right = TreeNode(2)
root.right.right = TreeNode(5)
print(all_path_sums(root, 22)) # [[5,4,11,2]]Yol Toplamı III: Herhangi Bir Yol, Herhangi Bir Düğüm
Yol Toplamı III (LeetCode #437), yolun yalnızca kökten yaprağa gitmek zorunda olmadığı ve herhangi bir yerden başlayıp bitebildiği, toplamı hedefe eşit yolları sayar. Kaba kuvvet yaklaşımının karmaşıklığı O(n²)'dir: her düğümden bir DFS çalıştırılır. En iyi O(n) yaklaşımı bir önek toplamı karma haritası kullanır: güncel toplamı takip eder ve current_sum - target ifadesinin daha önce kaç kez ortaya çıktığını sayar; bu, alt dizi toplamı yaklaşımına benzer.
def path_sum_iii(root, target):
prefix_counts = {0: 1}
def dfs(node, running_sum):
if not node:
return 0
running_sum += node.val
count = prefix_counts.get(running_sum - target, 0)
prefix_counts[running_sum] = prefix_counts.get(running_sum, 0) + 1
count += dfs(node.left, running_sum)
count += dfs(node.right, running_sum)
prefix_counts[running_sum] -= 1 # backtrack
return count
return dfs(root, 0)
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(-3)
root.left.left = TreeNode(3)
root.left.right = TreeNode(2)
root.right.right = TreeNode(11)
root.left.left.left = TreeNode(3)
root.left.left.right = TreeNode(-2)
root.left.right.right = TreeNode(1)
print(path_sum_iii(root, 8)) # 3En Düşük Ortak Ata Nedir?
İkili bir ağaçta iki p ve q düğümünün En Düşük Ortak Atası (LCA), hem p'yi hem de q'yu alt soyu olarak bulunduran en derin düğümdür (bir düğüm kendisinin alt soyu olabilir). LCA; “iki düğüm arasındaki uzaklık”, “iki düğüm arasındaki yol” ve BST aralık sorguları gibi problemlerde karşınıza çıkar. LCA'yı anlamak, orta düzey ağaç problemleri için çok önemlidir.
# 3
# / \
# 5 1
# / \ / \
# 6 2 0 8
# / \
# 7 4
# LCA(5, 1) = 3 (root)
# LCA(5, 4) = 5 (p itself is ancestor of q)
# LCA(6, 4) = 5
# LCA(7, 4) = 2
# Key insight: the LCA is the node where p and q
# first 'split' into different subtrees.
print('LCA: deepest node that is ancestor of both p and q')Özyinelemeli LCA Algoritması
Zarif özyinelemeli LCA çözümü, p veya q olan ya da alt ağaçlarında her ikisini de bulunduran ilk düğümü döndürür. Geçerli düğüm p veya q ise onu döndürün. Aksi halde sol ve sağ alt ağaçlarda özyinelemeli olarak ilerleyin. Her iki taraf da boş olmayan bir değer döndürürse geçerli düğüm LCA'dır. Yalnızca bir taraf boş olmayan bir değer döndürürse, bu sonucu yukarı aktarın. Bu yaklaşım O(n) zaman ve O(h) bellek kullanır.
def lowest_common_ancestor(root, p, q):
# Base case: empty or found one of the targets
if not root or root == p or root == q:
return root
# Search both subtrees
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
# If both sides found something, this node is the LCA
if left and right:
return root
# Otherwise, return whichever side found something
return left if left else right
root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left.left = TreeNode(6)
root.left.right = TreeNode(2)
p, q = root.left, root.right # 5 and 1
lca = lowest_common_ancestor(root, p, q)
print(lca.val) # 3Bir Düğümün Kendi Atası Olabildiği Durumda LCA
Kritik bir sınır durumu şudur: p, q'nun atasıysa (veya tersi), LCA p'nin kendisidir. Özyinelemeli algoritma bunu otomatik olarak ele alır — p'ye ulaştığında, p'nin alt ağaçlarına bakmadan hemen p'yi döndürür. Üst düğüm, bir tarafın p'yi, diğer tarafın ise boş değeri döndürdüğünü görür ve p'yi LCA olarak yukarı aktarır. LCA kodlarken bu durumu testlerinizle her zaman doğrulayın.
# Test case: p is ancestor of q
# Tree: 3 -> left=5 -> left=6
# LCA(5, 6) should be 5
root = TreeNode(3)
root.left = TreeNode(5)
root.left.left = TreeNode(6)
p = root.left # node 5
q = root.left.left # node 6
lca = lowest_common_ancestor(root, p, q)
print(lca.val) # 5 (p itself is the LCA)Üst Düğüm İşaretçileriyle LCA
Her düğümde bir üst düğüm işaretçisi varsa LCA, “iki bağlı listenin kesişimi” problemine dönüşür. p'nin atalarını bir kümede toplayın, ardından bu kümede bulunan bir düğüm bulana kadar q'dan başlayıp yukarı ilerleyin. O(h) zaman ve O(h) bellek kullanan bu yaklaşım, düğüm yapısını sizin belirlediğiniz ve üst düğüm başvurularını saklayabildiğiniz sistem tasarımı mülakatlarında yaygındır.
class NodeWithParent:
def __init__(self, val, parent=None):
self.val = val
self.parent = parent
self.left = None
self.right = None
def lca_with_parent(p, q):
ancestors = set()
# Collect all ancestors of p
node = p
while node:
ancestors.add(node)
node = node.parent
# Walk up from q until we hit a known ancestor
node = q
while node:
if node in ancestors:
return node
node = node.parent
return None
print('With parent pointers: O(h) time and space')İkili Arama Ağacında LCA
Bir BST'de LCA daha basittir; çünkü sıralama özelliği her düğümün hangi alt ağaçta bulunduğunu gösterir. p ve q'nun her ikisi de geçerli düğümden küçükse LCA sol alt ağaçtadır. İkisi de büyükse LCA sağ alt ağaçtadır. Aksi halde geçerli düğüm bu ikisini ayırdığı için LCA odur. Bu, dengeli BST'lerde problemi O(log n) karmaşıklığına indirir.
def lca_bst(root, p, q):
if not root:
return None
if p.val < root.val and q.val < root.val:
return lca_bst(root.left, p, q) # both in left
if p.val > root.val and q.val > root.val:
return lca_bst(root.right, p, q) # both in right
return root # split point = LCA
# Iterative BST LCA (no recursion overhead):
def lca_bst_iter(root, p, q):
while root:
if p.val < root.val and q.val < root.val:
root = root.left
elif p.val > root.val and q.val > root.val:
root = root.right
else:
return root
return None
print('BST LCA: O(log n) for balanced trees')İki Düğüm Arasındaki Uzaklık
Ağaçta iki düğüm arasındaki uzaklık, onları birbirine bağlayan yoldaki kenarların sayısına eşittir. Bu değer LCA kullanılarak doğrudan hesaplanır: distance(p, q) = depth(p) + depth(q) - 2 * depth(LCA(p,q)). Önce LCA'yı bulun, ardından her düğümün derinliğini sayın. Uygun bir yardımcıyla bu işlem O(n) zaman ve O(h) bellek kullanır.
def find_depth(root, target, depth=0):
if not root:
return -1
if root == target:
return depth
left = find_depth(root.left, target, depth + 1)
if left != -1:
return left
return find_depth(root.right, target, depth + 1)
def node_distance(root, p, q):
lca = lowest_common_ancestor(root, p, q)
# depth from LCA to p and q
dp = find_depth(lca, p)
dq = find_depth(lca, q)
return dp + dq
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(node_distance(root, root.left.left, root.left.right)) # 2Kökten Yaprağa En Büyük Toplamlı Yol
Kökten yaprağa en büyük toplamlı yol, kökten geçerli düğüme kadar olan güncel toplamı takip eder. Yapraklarda bu toplamı genel maksimumla karşılaştırın. Bu, geçerli yol toplamının parametre olarak aktarıldığı bir ön sıralı DFS işlemidir. Genel maksimum yol toplamından farklı olarak bu sürüm kökten yaprağa giden yollarla sınırlıdır; bu nedenle daha basittir ve düğümler arasındaki rastgele yolları dikkate almanız gerekmez.
def max_root_to_leaf_sum(root):
if not root:
return float('-inf')
best = [float('-inf')]
def dfs(node, running):
running += node.val
if not node.left and not node.right: # leaf
best[0] = max(best[0], running)
return
if node.left:
dfs(node.left, running)
if node.right:
dfs(node.right, running)
dfs(root, 0)
return best[0]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(max_root_to_leaf_sum(root)) # 1+2+5 = 8Kökten Yaprağa Sayıların Toplamı
Kökten yaprağa sayıların toplamı (LeetCode #129), her kökten yaprağa yolu bir ondalık sayı olarak ele alır (örneğin 1→2→3 yolu 123 sayısını temsil eder) ve bu sayıların toplamını ister. Sayıyı, current_number * 10 + node.val ifadesini özyineleme boyunca aşağı aktararak oluşturun. Her yaprakta tamamlanan sayıyı toplama ekleyin. Bu, birikimli durumun aşağı doğru aktarıldığı ön sıralı DFS işleminin temiz bir örneğidir.
def sum_numbers(root):
def dfs(node, num):
if not node:
return 0
num = num * 10 + node.val
if not node.left and not node.right: # leaf
return num
return dfs(node.left, num) + dfs(node.right, num)
return dfs(root, 0)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(sum_numbers(root)) # 12 + 13 = 25
root2 = TreeNode(4)
root2.left = TreeNode(9)
root2.right = TreeNode(0)
root2.left.left = TreeNode(5)
root2.left.right = TreeNode(1)
print(sum_numbers(root2)) # 495 + 491 + 40 = 1026Hızlı Kontrol
Bu dersteki Veri Yapıları & Algoritmalar — Kodlama Mülakatı Hazırlığı kavramlarını anlayıp anlamadığınızı test edin.
Ders Özeti
Bu derste şunları öğrendiniz: yol toplamı türleri (kökten yaprağa, tüm yollar ve önek toplamlarıyla yol toplamı III), zarif özyinelemeli bölme kullanarak en düşük ortak ata bulma ve sıralama özelliğini kullanarak O(log n) sürede BST LCA bulma. Sırada ekleme ve arama işlemleriyle İkili Arama Ağaçlarına başlıyoruz.
Sıkça Sorulan Sorular
“Yol Toplamı ve En Düşük Ortak Ata” dersi ücretsiz mi?
Evet — “Yol Toplamı ve En Düşük Ortak Ata” 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.
“Yol Toplamı ve En Düşük Ortak Ata” dersinde ne öğreneceğim?
Genel bir ikili ağaçta özyinelemeli iniş kullanarak kökten yaprağa yol toplamı, tüm yolların toplamı ve en düşük ortak ata problemlerini çözü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 4. dersidir.
“Yol Toplamı ve En Düşük Ortak Ata” 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