Jumlah Jalur dan Leluhur Bersama Terendah
Selesaikan jumlah jalur dari akar ke daun, jumlah semua jalur, dan lowest-common-ancestor untuk pohon biner umum menggunakan penelusuran rekursif.
Jumlah Jalur dan Leluhur Bersama Terendah adalah pelajaran DSA Interview Prep gratis di CoddyKit. Ini adalah pelajaran 4 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar DSA Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Jumlah Jalur dari Akar ke Daun
Masalah jumlah jalur menanyakan apakah ada jalur dari akar ke daun yang jumlahnya sama dengan target. Teruskan target yang tersisa dalam rekursi dengan mengurangi nilai setiap simpul. Pada simpul daun, periksa apakah nilai yang tersisa sama dengan nilai daun. Cara ini menghindari pemeliharaan daftar jalur secara eksplisit, sekaligus hemat ruang dan rapi. Kasus khusus: pohon kosong tidak memiliki jalur, jadi segera kembalikan False.
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->2Semua Jalur dari Akar ke Daun
Untuk mencatat semua jalur, pertahankan daftar jalur yang sedang dibangun. Pada setiap pemanggilan rekursif, gunakan append untuk menambahkan nilai simpul saat ini, lakukan rekursi ke simpul anak, lalu lakukan pop saat kembali (mundur untuk mencoba pilihan lain). Pada simpul daun, simpan salinan (list(path)) dari jalur saat ini. Pola ini — pilih, lakukan rekursi, batalkan pilihan — merupakan dasar penelusuran mundur pada pohon.
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]]Jumlah Jalur III: Jalur Apa Pun, Simpul Mana Pun
Jumlah Jalur III (LeetCode #437) menghitung jalur yang jumlahnya sama dengan target, dengan jalur yang dapat dimulai dan diakhiri di simpul mana pun (bukan hanya dari akar ke daun). Pendekatan naifnya memiliki kompleksitas O(n²): jalankan DFS dari setiap simpul. Pendekatan optimal O(n) menggunakan peta hash jumlah prefiks: lacak jumlah berjalan dan hitung berapa kali current_sum - target telah muncul sebelumnya, serupa dengan pendekatan jumlah sublarik.
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)) # 3Apa Itu Leluhur Bersama Terendah
Leluhur Bersama Terendah (LCA) dari dua simpul p dan q dalam pohon biner adalah simpul terdalam yang memiliki p dan q sebagai keturunan (sebuah simpul dapat menjadi keturunan dari dirinya sendiri). LCA muncul dalam masalah seperti "jarak antara dua simpul", "jalur antara dua simpul", dan kueri rentang BST. Memahami LCA sangat penting untuk menyelesaikan masalah pohon tingkat menengah.
# 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')Algoritma Rekursif LCA
Solusi rekursif LCA yang elegan mengembalikan simpul pertama yang merupakan p atau q, atau yang memiliki keduanya di subpohonnya. Jika simpul saat ini adalah p atau q, kembalikan simpul tersebut. Jika tidak, lakukan rekursi ke kiri dan kanan. Jika kedua sisi mengembalikan nilai yang tidak kosong, simpul saat ini adalah LCA. Jika hanya satu sisi yang mengembalikan nilai, teruskan hasil tersebut ke atas. Algoritma ini berjalan dalam waktu O(n) dan menggunakan ruang O(h).
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) # 3LCA Saat Simpul Dapat Menjadi Leluhurnya Sendiri
Kasus khusus yang penting: jika p adalah leluhur q (atau sebaliknya), LCA adalah p itu sendiri. Algoritma rekursif menanganinya secara otomatis — ketika mencapai p, algoritma segera mengembalikan p tanpa memeriksa subpohon p. Simpul induk akan melihat bahwa satu sisi mengembalikan p dan sisi lainnya tidak menghasilkan nilai, lalu meneruskan p ke atas sebagai LCA. Selalu verifikasi kasus ini melalui pengujian saat menulis kode LCA.
# 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)LCA dengan Penunjuk Induk
Jika setiap simpul memiliki penunjuk induk, LCA berubah menjadi masalah "irisan dua daftar tertaut". Kumpulkan leluhur p dalam sebuah himpunan, lalu telusuri ke atas dari q hingga menemukan simpul yang ada dalam himpunan tersebut. Pendekatan ini menggunakan waktu O(h) dan ruang O(h), serta umum digunakan dalam wawancara perancangan sistem ketika Anda mengendalikan struktur simpul dan dapat menyimpan referensi induk.
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')LCA pada BST
Dalam BST, LCA lebih sederhana karena properti pengurutan memberi tahu subpohon mana yang berisi setiap simpul. Jika p dan q lebih kecil daripada simpul saat ini, LCA berada di subpohon kiri. Jika keduanya lebih besar, LCA berada di subpohon kanan. Jika tidak, simpul saat ini memisahkan keduanya, sehingga simpul tersebut adalah LCA. Untuk BST seimbang, cara ini mengurangi kompleksitas masalah menjadi O(log n).
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')Jarak antara Dua Simpul
Jarak antara dua simpul dalam pohon sama dengan jumlah sisi pada jalur yang menghubungkan keduanya. Jarak ini dapat dihitung langsung dari LCA: distance(p, q) = depth(p) + depth(q) - 2 * depth(LCA(p,q)). Temukan LCA terlebih dahulu, lalu hitung kedalaman setiap simpul. Dengan fungsi pembantu yang tepat, algoritma ini berjalan dalam waktu O(n) dan menggunakan ruang O(h).
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)) # 2Jalur Akar-ke-Daun dengan Jumlah Maksimum
Jalur akar-ke-daun dengan jumlah maksimum melacak jumlah berjalan dari akar ke simpul saat ini. Pada simpul daun, bandingkan nilainya dengan maksimum keseluruhan. Ini adalah DFS praurutan yang meneruskan jumlah jalur saat ini sebagai parameter. Berbeda dari masalah jumlah jalur maksimum umum, versi ini dibatasi pada jalur akar-ke-daun, sehingga lebih sederhana — tidak perlu mempertimbangkan jalur sembarang dari satu simpul ke simpul lainnya.
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 = 8Menjumlahkan Angka dari Akar ke Daun
Menjumlahkan angka dari akar ke daun (LeetCode #129) memperlakukan setiap jalur dari akar ke daun sebagai angka desimal (misalnya, jalur 1→2→3 mewakili angka 123), lalu meminta jumlah semua angka tersebut. Bangun angka dengan meneruskan current_number * 10 + node.val dalam rekursi. Pada setiap simpul daun, tambahkan angka yang sudah lengkap ke jumlah keseluruhan. Ini adalah contoh yang rapi tentang DFS praurutan yang meneruskan keadaan terakumulasi ke bawah.
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 = 1026Pemeriksaan Singkat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini, Anda mempelajari: variasi jumlah jalur (dari akar ke daun, semua jalur, dan jumlah jalur III dengan jumlah prefiks), leluhur bersama terendah menggunakan pemisahan rekursif yang elegan, serta LCA BST dalam O(log n) menggunakan properti pengurutan. Selanjutnya kita mulai membahas Pohon Pencarian Biner dengan operasi penyisipan dan pencarian.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Jumlah Jalur dan Leluhur Bersama Terendah” gratis?
Ya — teks lengkap “Jumlah Jalur dan Leluhur Bersama Terendah” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus DSA Interview Prep, upgrade ke CoddyKit PRO. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Jumlah Jalur dan Leluhur Bersama Terendah”?
Selesaikan jumlah jalur dari akar ke daun, jumlah semua jalur, dan lowest-common-ancestor untuk pohon biner umum menggunakan penelusuran rekursif. Kamu berlatih DSA Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai DSA Interview Prep?
Tidak diperlukan pengalaman sebelumnya. DSA Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 4 dari 4.
Berapa lama pelajaran “Jumlah Jalur dan Leluhur Bersama Terendah” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran DSA Interview Prep ini?
Ya. Setiap pelajaran DSA Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Kelas TreeNode dan BFS Berdasarkan Level
- DFS In-Order, Pre-Order, dan Post-Order
- Diameter, Tinggi, dan Pohon Seimbang
- Jumlah Jalur dan Leluhur Bersama Terendah