Jumlah Laluan dan Leluhur Sepunya Terendah
Selesaikan jumlah laluan akar-ke-daun, jumlah semua laluan dan lowest-common-ancestor bagi pepohon binari umum menggunakan penurunan rekursif.
Jumlah Laluan dan Leluhur Sepunya Terendah ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 4 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Jumlah Laluan Akar ke Daun
Masalah jumlah laluan menanyakan sama ada terdapat laluan akar ke daun yang jumlahnya sama dengan sasaran. Hantarkan sasaran berbaki melalui rekursi dengan menolak nilai setiap nod. Pada nod daun, periksa sama ada nilai berbaki sama dengan nilai nod daun. Cara ini mengelakkan keperluan mengekalkan senarai laluan secara jelas, serta menggunakan ruang dengan cekap dan mudah difahami. Kes khas: pepohon kosong tidak mempunyai laluan, jadi pulangkan False dengan segera.
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 Laluan Akar ke Daun
Untuk menyenaraikan semua laluan, kekalkan senarai laluan yang sedang dibina. Dalam setiap panggilan rekursif, tambahkan nilai nod semasa, lakukan rekursi pada nod anak, kemudian keluarkan elemen terakhir apabila kembali (undur langkah). Pada nod daun, rekodkan salinan keadaan semasa (list(path)) bagi laluan tersebut. Pola ini — pilih, lakukan rekursi, batalkan pilihan — ialah asas pengunduran langkah pada pepohon.
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 Laluan III: Sebarang Laluan, Sebarang Nod
Path Sum III (LeetCode #437) mengira laluan yang jumlahnya sama dengan sasaran, dengan laluan itu boleh bermula dan berakhir di mana-mana sahaja (bukan hanya dari akar ke daun). Pendekatan naif mengambil masa O(n²): jalankan DFS dari setiap nod. Pendekatan optimum O(n) menggunakan peta cincangan jumlah awalan: jejaki jumlah semasa dan kira berapa kali current_sum - target pernah muncul sebelum ini, selaras dengan pendekatan jumlah subtatasusunan.
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)) # 3Apakah Leluhur Sepunya Terendah?
Leluhur Sepunya Terendah (LCA) bagi dua nod p dan q dalam pepohon binari ialah nod paling dalam yang mempunyai p dan q sebagai keturunannya (sesuatu nod boleh menjadi keturunan dirinya sendiri). LCA muncul dalam masalah seperti “jarak antara dua nod”, “laluan antara dua nod” dan pertanyaan julat BST. Memahami LCA amat penting untuk masalah pepohon peringkat pertengahan.
# 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 LCA Rekursif
Penyelesaian LCA rekursif yang elegan mengembalikan nod pertama yang sama ada p atau q, atau nod yang mempunyai kedua-duanya dalam subpepohonnya. Jika nod semasa ialah p atau q, pulangkan nod itu. Jika tidak, lakukan rekursi ke kiri dan ke kanan. Jika kedua-dua sisi mengembalikan nilai bukan kosong, nod semasa ialah LCA. Jika hanya satu sisi mengembalikan nilai bukan kosong, hantarkan hasil itu ke atas. Ini mengambil masa O(n) dan 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 Apabila Nod Boleh Menjadi Leluhurnya Sendiri
Kes khas yang penting: jika p ialah leluhur q (atau sebaliknya), LCA ialah p sendiri. Algoritma rekursif mengendalikan keadaan ini secara automatik — apabila mencapai p, algoritma terus memulangkan p tanpa melihat ke dalam subpepohon p. Nod induk akan mendapati bahawa satu sisi mengembalikan p manakala sisi yang satu lagi mengembalikan nilai kosong, lalu menghantar p ke atas sebagai LCA. Sentiasa sahkan kes ini melalui ujian anda apabila menulis kod 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 Penuding Induk
Jika setiap nod mempunyai penuding induk, LCA menjadi masalah “persilangan dua senarai terpaut”. Kumpulkan leluhur p dalam satu set, kemudian bergerak ke atas dari q sehingga menemui nod yang terdapat dalam set itu. Pendekatan ini mengambil masa O(h) dan ruang O(h), serta lazim digunakan dalam temu duga reka bentuk sistem apabila anda mengawal struktur nod dan boleh menyimpan rujukan kepada nod 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 dalam Pepohon Carian Binari
Dalam BST, LCA lebih mudah kerana sifat susunan memberitahu anda subpepohon yang mengandungi setiap nod. Jika p dan q kedua-duanya lebih kecil daripada nod semasa, LCA berada dalam subpepohon kiri. Jika kedua-duanya lebih besar, LCA berada dalam subpepohon kanan. Jika tidak, nod semasa memisahkan kedua-duanya, maka nod itu ialah LCA. Ini mengurangkan masalah kepada O(log n) untuk BST yang seimbang.
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 Nod
Jarak antara dua nod dalam pepohon sama dengan bilangan sisi pada laluan yang menghubungkan kedua-duanya. Jarak ini boleh dikira secara langsung daripada LCA: distance(p, q) = depth(p) + depth(q) - 2 * depth(LCA(p,q)). Cari LCA terlebih dahulu, kemudian kira kedalaman setiap nod. Dengan fungsi pembantu yang sesuai, proses ini mengambil masa O(n) dan 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)) # 2Laluan Jumlah Maksimum dari Akar ke Daun
Laluan jumlah maksimum dari akar ke daun menjejaki jumlah semasa dari akar ke nod semasa. Pada nod daun, bandingkan jumlah itu dengan nilai maksimum global. Ini ialah DFS pra tertib yang menghantar jumlah laluan semasa sebagai parameter. Berbeza daripada jumlah laluan maksimum umum, versi ini terhad kepada laluan dari akar ke daun, jadi lebih mudah — tidak perlu mempertimbangkan laluan sewenang-wenangnya antara dua nod.
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 = 8Jumlah Nombor Akar ke Daun
Jumlah nombor akar ke daun (LeetCode #129) menganggap setiap laluan akar ke daun sebagai nombor perpuluhan (contohnya, laluan 1→2→3 mewakili nombor 123) dan meminta jumlah kesemuanya. Bina nombor itu dengan menghantar current_number * 10 + node.val melalui rekursi. Pada setiap nod daun, tambahkan nombor yang lengkap kepada jumlah keseluruhan. Ini ialah contoh jelas DFS pra tertib yang menghantar keadaan terkumpul 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 = 1026Semakan Pantas
Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.
Ulang Kaji Pelajaran
Dalam pelajaran ini, anda telah mempelajari: variasi jumlah laluan (akar ke daun, semua laluan, dan jumlah laluan III dengan jumlah awalan), leluhur sepunya terendah menggunakan pemisahan rekursif yang elegan, serta LCA BST dalam O(log n) menggunakan sifat susunan. Seterusnya, kita akan memulakan Pepohon Carian Binari dengan operasi penyisipan dan carian.
Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 90
- Pelajaran
- 360
Soalan Lazim
Adakah pelajaran “Jumlah Laluan dan Leluhur Sepunya Terendah” percuma?
Ya — teks penuh “Jumlah Laluan dan Leluhur Sepunya Terendah” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Jumlah Laluan dan Leluhur Sepunya Terendah”?
Selesaikan jumlah laluan akar-ke-daun, jumlah semua laluan dan lowest-common-ancestor bagi pepohon binari umum menggunakan penurunan rekursif. Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 4 daripada 4.
Berapa lamakah pelajaran “Jumlah Laluan dan Leluhur Sepunya Terendah” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?
Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Kelas TreeNode dan BFS Mengikut Aras
- DFS Dalam Susunan, Pra-Susunan dan Pasca-Susunan
- Diameter, Ketinggian dan Pepohon Seimbang
- Jumlah Laluan dan Leluhur Sepunya Terendah