Path Sum

Q: Berapa kompleksitas waktu Path Sum?

O(n) : setiap node dikunjungi paling banyak satu kali, dan pencarian dapat berhenti pada daun pertama yang cocok. Ruang tambahan adalah O(h) untuk jalur yang sedang dijelajahi, berupa bingkai pemanggilan atau entri pada stack milikmu sendiri.

MudahTree traversal

+10

Kamu mendapatkan sebuah binary tree yang disimpan dalam array tree dengan urutan level, dan sebuah angka targetSum. Akar berada di indeks 0, anak dari node pada indeks i berada di 2*i+1 (kiri) dan 2*i+2 (kanan), -1 menandai posisi kosong, dan array mungkin diakhiri dengan entri -1 tambahan. Kembalikan true jika ada jalur dari akar ke bawah hingga daun yang nilainya jika dijumlahkan sama dengan targetSum, dan false jika tidak. Daun adalah node yang kedua posisi anaknya kosong.

Fungsi

hasPathSum(tree: integer-array, targetSum: integer) → boolean

treeinteger-array: pohon biner dalam urutan level, dengan -1 untuk posisi kosong
targetSuminteger: jumlah yang harus dicapai oleh jalur dari akar ke daun
Mengembalikanboolean: true jika ada jalur dari akar ke daun yang jumlahnya sama dengan targetSum, false jika tidak

Batasan

1 ≤ tree.length ≤ 32767
Setiap tree[i] bernilai -1 atau suatu nilai dengan 0 ≤ tree[i] ≤ 1000.
tree[0] tidak pernah -1, jadi tree memiliki setidaknya satu node.
The array mungkin berakhir dengan entri -1 tambahan setelah simpul terakhir.
Kedua anak dari posisi kosong juga kosong, dan kedalamannya paling banyak 14.
0 ≤ targetSum ≤ 15000

Contoh

Input: tree = [3, 9, 6, -1, 2, 1, 7]targetSum = 14
Output: true
Penjelasan: Jalur 3, 9, 2 (indeks 0, 1, 4) berjumlah 14, dan 2 pada indeks 4 adalah daun.

Input: tree = [3, 9, 6, -1, 2, 1, 7]targetSum = 12
Output: false
Penjelasan: 3 + 9 = 12, tetapi 9 memiliki anak, jadi tidak ada jalur yang berakhir di sana. Jumlah tiga jalur dari akar ke daun adalah 14, 10, dan 16, dan tidak ada yang berjumlah 12.

Input: tree = [4, -1, -1]targetSum = 4
Output: true
Penjelasan: Kedua posisi anak dari root kosong, jadi root adalah leaf. Jalur yang hanya berisi 4 memiliki jumlah 4.

Pertanyaan lanjutan

Bisakah kamu menghitung jumlah jalur yang totalnya targetSum jika jalur dapat dimulai dari simpul mana pun dan berakhir di simpul mana pun di bawahnya?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Hanya path lengkap yang dihitung, dari root sampai leaf. Jumlah sementara bisa mencapai targetSum pada node yang masih memiliki child, tetapi itu tidak dihitung. Jadi, teruskan jumlah path ke setiap node, sebagai parameter atau di dalam stack, lalu bandingkan dengan target hanya pada leaf.

Rekursi pada jumlah yang tersisa

Intuisi

Jalur yang jumlahnya sama dengan targetSum dimulai dari nilai root, jadi sisa jalur itu, yang dimulai dari salah satu anak root, harus berjumlah targetSum dikurangi nilai tersebut. Itu pertanyaan yang sama pada pohon yang lebih kecil. Kurangi nilai setiap node saat menelusuri ke bawah. Di leaf, jalur berakhir, jadi jawabannya adalah apakah tidak ada nilai yang tersisa.

Pada contoh pertama, root menyisakan 14 - 3 = 11, node 9 menyisakan 2, dan leaf 2 menyisakan 0. Pada contoh kedua, node 9 sudah menyisakan 0, tetapi node itu memiliki anak, jadi pencarian berlanjut. Setiap node dikunjungi sekali, dengan waktu O(n), dan call stack menyimpan satu frame untuk setiap level, paling banyak 15.

Algoritma

Tulis walk(i, remaining) dan kurangi tree[i] dari remaining.
Jika kedua posisi anak dari i kosong (indeks melewati akhir atau -1), kembalikan apakah remaining bernilai 0.
Jika tidak, kembalikan true jika pemanggilan walk pada anak kiri yang ada atau anak kanan yang ada mengembalikan true.
Kembalikan walk(0, targetSum).

def hasPathSum(tree, targetSum):
    n = len(tree)

    def walk(i, remaining):
        # remaining is what the path still needs once it reaches node i.
        remaining -= tree[i]
        left, right = 2 * i + 1, 2 * i + 2
        has_left = left < n and tree[left] != -1
        has_right = right < n and tree[right] != -1
        if not has_left and not has_right:
            return remaining == 0  # a leaf: the path ends here
        return (has_left and walk(left, remaining)) or (has_right and walk(right, remaining))

    return walk(0, targetSum)

Pencarian mendalam terlebih dahulu dengan stack eksplisit

Intuisi

Rekursi menyimpan satu angka untuk setiap pemanggilan. Simpan sendiri angka tersebut di stack di samping setiap node: jumlah jalur dari root hingga node tersebut. Mulai dengan (0, tree[0]); setiap anak mendapat jumlah milik induknya ditambah nilainya sendiri. Ambil satu pasangan dari stack. Jika node tersebut adalah daun dengan jumlah targetSum, kamu selesai; jika tidak, masukkan anak-anaknya yang sebenarnya ke stack.

Setiap node yang sebenarnya dimasukkan sekali, dengan waktu O(n), dan stack menyimpan sekitar satu saudara yang menunggu di setiap tingkat, dengan O(h). Perulangan yang sama berfungsi pada tree berbasis pointer yang dalam, tempat rekursi bisa kehabisan stack.

Algoritma

Masukkan (0, tree[0]) ke dalam stack.
Keluarkan sepasang (i, total) dari stack, lalu periksa posisi anak 2*i+1 dan 2*i+2.
Jika kedua anak tidak nyata dan total sama dengan targetSum, kembalikan true.
Masukkan setiap anak nyata c sebagai (c, total + tree[c]).
Jika stack kosong, kembalikan false.

def hasPathSum(tree, targetSum):
    n = len(tree)
    stack = [(0, tree[0])]  # (node index, sum of the path from the root to it)
    while stack:
        i, total = stack.pop()
        left, right = 2 * i + 1, 2 * i + 2
        has_left = left < n and tree[left] != -1
        has_right = right < n and tree[right] != -1
        if not has_left and not has_right and total == targetSum:
            return True  # a leaf whose path adds up
        if has_left:
            stack.append((left, total + tree[left]))
        if has_right:
            stack.append((right, total + tree[right]))
    return False

Jebakan dan kasus tepi

Membandingkan jumlah pada setiap node. Pada contoh kedua, 3 + 9 = 12 cocok pada 9, yang memiliki child, jadi jawabannya false.
Menganggap tempat child yang kosong sebagai akhir jalur. Jadi, 9 pada contoh kedua mengakhiri jalur melalui tempat child kiri yang kosong.
Melupakan root saja. Satu node adalah leaf, jadi [4] dengan target 4 bernilai true, begitu juga [0] dengan target 0.
Membaca melewati akhir array. Leaf yang berada dekat akhir dapat memiliki indeks child yang melewati entri terakhir.
Keliru menangani offset di Lua dan R. Pertahankan indeks node berbasis 0 untuk 2*i+1 dan baca tree[i + 1].

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu Path Sum?

O(n): setiap node dikunjungi paling banyak satu kali, dan pencarian dapat berhenti pada daun pertama yang cocok. Ruang tambahan adalah O(h) untuk jalur yang sedang dijelajahi, berupa bingkai pemanggilan atau entri pada stack milikmu sendiri.

Apakah Path Sum bisa diselesaikan dengan BFS?

Ya. Masukkan pasangan node dan jumlah lintasannya ke dalam queue, bukan stack, lalu periksa setiap daun saat dikeluarkan. Kompleksitas waktunya tetap O(n), tetapi queue dapat menampung satu level penuh, sekitar setengah jumlah node pada pohon penuh, sedangkan stack menampung sekitar satu node per level.

Bagaimana cara menemukan setiap jalur yang jumlahnya sama dengan target?

Simpan daftar node pada jalur saat ini saat kamu menelusuri ke bawah, salin daftar itu ke dalam jawaban pada setiap daun yang jumlahnya cocok, lalu hapus node terakhir saat kamu kembali ke atas. Penelusurannya tetap sama. Menyalin jalur bisa memerlukan biaya lebih besar daripada penelusuran ketika banyak daun cocok.

def hasPathSum(tree, targetSum):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

tree = [3, 9, 6, -1, 2, 1, 7]
targetSum = 14

Output yang diharapkan

true