Left View of Binary Tree
Yığın sırasındaki root dizisi olarak bir ikili ağaç veriliyor: kök 0 indeksindedir, i indeksindeki düğümün çocukları 2*i+1 (sol) ve 2*i+2 (sağ) indekslerindedir ve boş konumları -1 belirtir. Dizinin sonunda fazladan -1 girdileri bulunabilir.
Ağacın solunda durun. Her seviyede bir düğüm görürsünüz: en soldakini; seviyenin geri kalanı onun arkasında gizlenir. Gördüğünüz değerleri üst seviyeden aşağıya doğru döndürün.
Fonksiyon
- rootinteger-array
- heap düzenindeki ağaç; boş bir konum için -1
- Döndürürinteger-array
- Her seviyenin en soldaki değeri; önce en üst seviye
Kısıtlar
1 ≤ root.length ≤ 32767- Her
root[i],-1ya da0 ≤ root[i] ≤ 104aralığında bir değerdir. - Düğüm değerleri birbirinden farklıdır.
root[0]hiçbir zaman-1değildir, bu yüzden ağaçta en az bir düğüm vardır.- Dizi, son düğümden sonra fazladan
-1girdileriyle bitebilir. - Boş bir konumun her iki çocuğu da boştur ve ağacın en fazla
14seviyesi vardır.
Örnekler
- Girdi
- root = [3, 8, 5, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, 1]
- Çıktı
- [3, 8, 6, 1]
- Açıklama
8bir yaprak olduğundan, üçüncü ve dördüncü seviyelerde yalnızca6(indeks 6) ve1(indeks 13) bulunur; ikisi de sağ çocuk5'in altındadır. Yine de onları görürsün:[3, 8, 6, 1].
- Girdi
- root = [10, -1, -1]
- Çıktı
- [10]
- Açıklama
- 1 ve 2 indisleri
-1değerini içeriyor, bu nedenle10öğesinin çocuğu yok ve görünüm yalnızca kökten oluşuyor.
- Girdi
- root = [1, 2, 3, 4, 5, 6, 7]
- Çıktı
- [1, 2, 4]
- Açıklama
- Üç seviyeli tam bir ağaç. Seviyelerin en soldaki konumlarının indeksleri 0, 1 ve 3'tür; bu konumlarda
1,2ve4bulunur.
Ek soru
Seviye d, 2^d-1 ile 2^(d+1)-2 arasındaki dizinleri doldurur. Kuyruk veya özyineleme kullanmadan bu aralıkları tarayarak görünümü oluşturabilir misin? Bu, doldurulmuş bir dizide ne kadara mal olur?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Bir düzeyde gördüğünüz düğüm her zaman sol çocuk değildir. 1. örnekte üçüncü düzeyde hangi düğümü görüyorsunuz ve bu kimin çocuğudur?
Düğümleri seviyelerine göre gruplayın. Her seviyeyi soldan sağa ziyaret ederseniz, aradığınız düğüm o seviyede karşılaştığınız ilk düğümdür.
Bir kuyruğu her turda bir düzey işle ve her turun ilk düğümünü sakla. Ya da derinlik öncelikli olarak ilerle, derinliği taşı, önce sola sonra sağa git ve derinliği şimdiye kadar kaydedilen değerlerin sayısına eşit olduğunda bir düğümü kaydet.
Çözüm
Kökten başlayarak sol çocukları takip etmek, sol alt ağaç daha kısa olduğunda başarısız olur: ilk örnekte alt seviyeler sağ alt ağaç üzerinden görülür. Her seviyenin ilk düğümünü istersin. Genişlik öncelikli arama, her seviyeyi soldan sağa verir; önce sola giden derinlik öncelikli bir dolaşım, her seviyenin en soldaki düğümüne önce ulaşır.
Genişlik öncelikli, her seviyenin ilk düğümü
Sezgi
Turlara göre işlenen bir kuyruk, seviyeleri sana teker teker verir. Bir turun başında kuyrukta soldan sağa tam olarak bir seviye bulunur; çünkü tur sırasında eklenen her çocuk onun arkasına gelir. O seviyedeki indeks sayısı kadar öğeyi kuyruktan çıkar, her birinin çocuklarını önce solu gelecek şekilde kuyruğa ekle ve ilk değeri sakla.
İlk örnekte turlar [3], [8, 5], [6] ve [1] şeklindedir ve sırasıyla 3, 8, 6 ve 1 değerlerini saklarlar. Çocuklarının bulunduğu 3 ve 4 numaralı konumlarda -1 olduğu için 8 hiçbir şey eklemez.
Her düğüm kuyruğa bir kez girer ve bir kez çıkar: O(n) zaman. Kuyruk, 14 seviyeli tam bir ağaçta 8192 indekse kadar, bir seviyenin tamamını tutar.
Algoritma
0indeksini tutan bir kuyruk ve boş bir yanıt oluştur.- Kuyruk boş değilken,
sdeğerini kuyruğun boyutu olarak belirle vesindeks çıkar. İlk indeksin değerini ekle. - Çıkarılan her
iindeksi için, dizinin sonunu aşan indeksleri ve-1değerine eşit girdileri atlayarak önce2i+1, sonra2i+2indekslerini kuyruğa ekle.
from collections import deque
def leftView(root):
n = len(root)
view = []
queue = deque([0]) # node indexes; the root is never empty
while queue:
size = len(queue) # exactly the nodes of the current level
for j in range(size):
i = queue.popleft()
if j == 0:
view.append(root[i]) # the first node of this level
for child in (2 * i + 1, 2 * i + 2):
if child < n and root[child] != -1:
queue.append(child)
return viewÖnce derinlemesine, önce sol çocuk
Sezgi
Önce sol alt ağda, sonra sağ alt ağaçta derinlik öncelikli dolaş ve her düğümün derinliğini aktar. Dolaşmanın d derinliğinde ulaştığı ilk düğüm, d seviyesinin en solundaki düğümdür. Bir seviyenin en solundaki x düğümünü ve onun sağındaki herhangi bir y düğümünü al: yollarının son ortak düğümünde x sola, y sağa gider ve dolaşma sağa dönmeden önce sol dalı tamamlar.
Dolaşma her seferinde bir seviye aşağı iner; bu nedenle d derinliğine ilk ulaştığında yanıt tam olarak d değer içerir. d yanıtın uzunluğuna eşit olduğunda düğümü kaydet; ziyaret edilen derinlikler kümesine gerek yoktur.
Her düğüm bir kez ziyaret edilir; zaman karmaşıklığı O(n)'dir ve bellek, her seviye için bir çağrı tutar; burada en fazla 14 çağrı olur. R sürümü kendi yığınını tutar ve sağ çocuğu sol çocuktan önce yığına ekler.
Algoritma
- Boş bir yanıt oluştur ve
visit(0, 0)çağrısını yap. visit(i, d)içinde,idizinin dışındaysa veyaroot[i]-1ise hemen dön.dyanıtın uzunluğuna eşitse, dolaşım ilk kezddüzeyine ulaşmıştır:root[i]değerini ekle.- Önce
visit(2i+1, d+1), ardındanvisit(2i+2, d+1)çağrısını yap. - İlk çağrı tamamlandığında yanıtı döndür.
def leftView(root):
n = len(root)
view = []
def visit(i, depth):
if i >= n or root[i] == -1:
return
if depth == len(view): # the first node met on this level
view.append(root[i])
# Left before right, so the leftmost node of every level comes first.
visit(2 * i + 1, depth + 1)
visit(2 * i + 2, depth + 1)
visit(0, 0)
return view
Tuzaklar ve uç durumlar
- Kökten başlayarak yalnızca sol çocukları izlemek. İlk örnekte bu,
8noktasında durur ve6ile1değerlerini kaçırır. - Her seviyenin ilk yuvasını,
root[2^d-1], okumak. İlk örnekte üçüncü seviyenin ilk yuvasında, indeks 3'te,-1bulunurken tek düğümü indeks 6'dadır. - Derinlik öncelikli gezinmede önce sağ çocuğu ziyaret etmek. Böylece her seviyede karşılaşılan ilk düğüm en sağdaki olur.
- Sınır kontrolü yapmadan bir çocuğu okumak. İndeks 13'teki
1değerinin çocuk yuvaları 27 ve 28'dir; bunlar 14 elemanlı dizinin sonunu aşar.
Sıkça sorulan sorular3
Sol görünüm bir ağacın sol sınırıyla aynı mıdır?
Hayır. Sol sınır bir yoldur: kökün sol çocuğundan başlar, gidebildiği zaman sola, aksi hâlde sağa gider ve bir yaprağa ulaşmadan durur. Sol görünüm, herhangi bir daldan her seviyede bir düğüm alır. İlk örnekte sınır boştur, çünkü 8 bir yapraktır; ancak görünümde 8, 6 ve 1 yer alır.
Sol görünümün zaman ve alan karmaşıklığı nedir?
Her iki çözüm de her düğümü bir kez ziyaret eder, bu nedenle zaman karmaşıklığı O(n) olur. Genişlik öncelikli kuyruğu, tam bir ağacın düğümlerinin yaklaşık yarısı kadar olan bir seviyenin tamamını tutar. Soldan önce yürüyüş, seviye başına bir çağrı tutar; h seviye için O(h).
Doğru görünümü elde etmek için çözümü nasıl değiştirirsin?
Genişlik öncelikli sürümde her turun ilk değeri yerine son değerini tut. Derinlik öncelikli sürümde sağ çocuğu sol çocuktan önce ziyaret et; böylece gezinmenin her düzeyde ulaştığı ilk düğüm en sağdaki olur.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def leftView(root):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argüman
root = [3, 8, 5, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, 1]
Beklenen Çıktı
[3, 8, 6, 1]