Maximum Depth of Binary Tree
Kamu mendapatkan binary tree yang disimpan dalam array tree dengan urutan level. Root berada pada indeks 0, anak dari node pada indeks i berada pada 2*i+1 (kiri) dan 2*i+2 (kanan), -1 menandai tempat kosong, dan array dapat diakhiri dengan entri -1 tambahan. Kembalikan kedalaman maksimum tree: jumlah node pada jalur terpanjang dari root hingga leaf.
Fungsi
- treeinteger-array
- pohon biner dalam urutan level, dengan -1 untuk posisi kosong
- Mengembalikaninteger
- jumlah node pada jalur terpanjang dari akar ke daun
Batasan
1 ≤ tree.length ≤ 32767- Setiap
tree[i]adalah-1atau nilai dengan0 ≤ tree[i] ≤ 1000. tree[0]tidak pernah-1, jadi tree memiliki setidaknya satu node.- Array dapat diakhiri dengan entri
-1tambahan setelah node terakhir. - Kedua anak dari posisi kosong juga kosong, dan kedalamannya paling banyak
14.
Contoh
- Input
- tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
- Output
- 4
- Penjelasan
- Jalur terpanjang adalah
5,8,3,6(indeks0,1,4,9), yang memiliki 4 simpul. Jalur melalui1berhenti setelah 2 simpul.
- Input
- tree = [7, -1, -1]
- Output
- 1
- Penjelasan
- Dua entri
-1adalah posisi anak kosong pada root. Root saja merupakan jalur yang terdiri dari satu node, jadi kedalamannya adalah1, bukan0.
- Input
- tree = [2, -1, 9, -1, -1, -1, 4]
- Output
- 3
- Penjelasan
- Root
2tidak memiliki anak kiri. Anak kanannya,9pada indeks2, memiliki4pada indeks6sebagai anak kanannya, membentuk jalur yang terdiri dari 3 simpul.
Pertanyaan lanjutan
Bagaimana kamu akan mengembalikan nilai-nilai pada jalur dari akar ke daun terpanjang sekaligus panjangnya? Jika beberapa jalur memiliki panjang yang sama, jalur mana yang akan kamu kembalikan?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Pikirkan tentang root. Jika kamu mengetahui kedalaman subtree kiri dan kedalaman subtree kanan, berapa kedalaman seluruh tree?
Nilainya adalah
1untuk root ditambah kedalaman yang lebih besar dari kedua subtree, dan posisi kosong memiliki kedalaman0. Aturan yang sama berlaku pada setiap node, jadi traversal yang mengetahui kedalaman setiap node dapat menemukan jawabannya.Simpan stack berisi pasangan indeks node dan kedalamannya, dimulai dari root dengan kedalaman 1. Keluarkan satu pasangan, ingat kedalaman terbesar yang ditemukan, lalu masukkan setiap child pada
2*i+1dan2*i+2yang berada di dalam array dan bukan-1, dengan kedalaman ditambah satu.
Solusi
Kedalaman ditentukan oleh cabang terpanjang, dan kamu tidak bisa tahu cabang mana yang terpanjang tanpa mengunjungi setiap node. Jadi, kamu perlu satu penelusuran penuh yang mengetahui seberapa dalam posisinya di setiap node. Rekursi, pencarian breadth-first berdasarkan level, dan pencarian depth-first dengan stack buatanmu masing-masing bisa melakukannya dalam satu kali penelusuran.
Rekursi pada dua subtree
Intuisi
Simpul anak dianggap ada jika indeksnya berada di dalam array dan nilainya bukan -1. Jalur terdalam melalui sebuah simpul turun ke subtree yang lebih dalam, jadi kedalaman pada indeks i adalah 1 untuk simpul tersebut ditambah kedalaman yang lebih besar pada 2*i+1 dan 2*i+2. Posisi kosong memiliki kedalaman 0, yang mengakhiri rekursi. Simpul daun mendapat 1 + max(0, 0) = 1, dan nilainya naik kembali ke akar.
Setiap simpul dikunjungi sekali. Call stack menyimpan satu frame untuk setiap tingkat jalur saat ini, O(h), paling banyak 14 di sini.
Algoritma
- Tulis
depth(i): jikaiberada setelah akhir array atautree[i]adalah-1, kembalikan0. - Jika tidak, kembalikan
1 + max(depth(2*i+1), depth(2*i+2)). - Kembalikan
depth(0).
def maxDepth(tree):
def depth(i):
# An index past the end or a -1 is an empty spot: depth 0.
if i >= len(tree) or tree[i] == -1:
return 0
return 1 + max(depth(2 * i + 1), depth(2 * i + 2))
return depth(0)Pencarian breadth-first, tingkat demi tingkat
Intuisi
Kedalaman maksimum adalah jumlah level, jadi kamu bisa menghitung level alih-alih mengikuti jalur. Antrean mengunjungi node berdasarkan urutan level. Sebelum setiap kelompok, baca ukuran antrean: node-node itu tepat satu level, karena anak-anak yang kamu tambahkan selama kelompok tersebut akan masuk di belakangnya. Setiap kelompok menambah kedalaman sebanyak 1. Pada contoh pertama, kelompok-kelompoknya adalah [5], [8, 1], [3], dan [6], jadi jawabannya adalah 4.
Antrean menampung satu level setiap kalinya, O(w) untuk level terlebar. Pada pohon penuh dengan kedalaman 14, jumlahnya 8192 dari 16383 node.
Algoritma
- Masukkan indeks root
0ke dalam antrean dan aturdepth = 0. - Selama antrean tidak kosong, tambahkan
1kedepthdan baca ukuran antrean. - Keluarkan indeks sebanyak itu. Untuk setiap indeks, masukkan indeks anak
2*i+1dan2*i+2yang berada di dalam array dan bukan-1ke dalam antrean. - Saat antrean kosong, kembalikan
depth.
from collections import deque
def maxDepth(tree):
n = len(tree)
queue = deque([0])
depth = 0
while queue:
depth += 1
for _ in range(len(queue)): # exactly the nodes of this level
i = queue.popleft()
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
queue.append(child)
return depthPencarian depth-first dengan stack eksplisit
Intuisi
Simpan tumpukan pasanganmu sendiri, yaitu indeks simpul dan kedalamannya, karena tidak ada hal lain yang mengingat seberapa jauh posisi suatu simpul. Mulai dengan (0, 1), akar pada kedalaman 1. Setiap simpul dimasukkan ke tumpukan sekali, dengan panjang jalur yang mencapainya, sehingga kedalaman terbesar yang kamu keluarkan dari tumpukan adalah jawabannya. Pada contoh pertama, 6 dimasukkan sebagai (9, 4).
Tumpukan menampung kira-kira satu simpul saudara yang tertunda per tingkat, O(h), tanpa tumpukan pemanggilan yang bisa meluap. Kode yang sama berfungsi pada pohon berbasis pointer dengan kedalaman berapa pun.
Algoritma
- Masukkan
(0, 1)ke dalam stack dan tetapkanbest = 0. - Ambil pasangan
(i, depth)dari stack dan tetapkanbestke nilai yang lebih besar antarabestdandepth. - Untuk setiap indeks anak
2*i+1dan2*i+2yang berada di dalam array dan bukan-1, masukkan indeks tersebut bersamadepth + 1. - Ulangi sampai stack kosong, lalu kembalikan
best.
def maxDepth(tree):
n = len(tree)
best = 0
stack = [(0, 1)] # (node index, depth of that node); the root is never empty
while stack:
i, depth = stack.pop()
best = max(best, depth)
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
stack.append((child, depth + 1))
return best
Jebakan dan kasus tepi
- Menghitung sisi, bukan node.
[7, -1, -1]memiliki kedalaman1, bukan0. - Melewatkan pemeriksaan batas. Pada contoh pertama,
6di indeks 9 memiliki indeks anak 19 dan 20, yang berada di luar batas array. Periksachild < nsebelum membacatree[child]. - Menghitung kedalaman dari panjang array. Entri
-1di bagian akhir mencapai level tanpa node:[7, -1, -1]memiliki panjang 3, tetapi kedalamannya 1. - Membaca ukuran antrean di dalam perulangan batch. Anak yang ditambahkan selama batch mengubah ukurannya, jadi simpan ukurannya terlebih dahulu.
- Keliru menggunakan offset di Lua dan R, yang array-nya dimulai dari 1. Pertahankan indeks node berbasis 0 untuk
2*i+1dan bacatree[i + 1].
Pertanyaan yang sering diajukan3
Apa kompleksitas waktu dari Kedalaman Maksimum Pohon Biner?
Setiap pendekatan mengunjungi setiap simpul satu kali, jadi kompleksitas waktunya O(n). Versi penelusuran mendalam menggunakan ruang tambahan O(h) untuk jalur saat ini, dengan h sebagai kedalamannya. Versi penelusuran melebar menggunakan O(w) untuk tingkat terlebar, sekitar setengah jumlah simpul pada pohon penuh.
Sebaiknya kamu menggunakan DFS atau BFS untuk mencari kedalaman maksimum pohon biner?
Keduanya berjalan dalam waktu O(n). Pencarian mendalam lebih singkat untuk ditulis dan menggunakan memori sebanding dengan kedalamannya, sehingga cocok untuk pohon yang lebar dan dangkal. Pencarian melebar menghitung level secara langsung dan menggunakan memori sebanding dengan level terlebarnya, sehingga cocok untuk pohon yang dalam dan sempit. Untuk kedalaman minimum, BFS lebih unggul karena dapat berhenti saat menemukan daun pertama.
Apa perbedaan antara kedalaman dan tinggi pohon biner?
Kedalaman sebuah node menghitung langkah dari root ke node tersebut; tinggi menghitung langkah dari node tersebut ke leaf terdalamnya. Kedalaman maksimum pohon sama dengan tinggi root. Soal ini menghitung node, jadi satu node memiliki kedalaman 1; menghitung edge menghasilkan nilai satu lebih sedikit.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def maxDepth(tree):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
Output yang diharapkan
4