Boundary Traversal of Binary Tree
root dizisi, ikili ağacı seviye sırasına göre tutar: kök 0 indeksinde, i indeksindeki düğümün çocukları 2i+1 (sol) ve 2i+2 (sağ) indekslerinde, boş bir konum için -1 bulunur ve sonda fazladan -1 girdileri olabilir. Yaprak, çocuğu olmayan bir düğümdür.
Sınırı kökten başlayarak saat yönünün tersine döndür:
- Kök.
- Sol sınır, yukarıdan aşağıya: kökün sol çocuğundan başlayarak, varsa sol çocuğa, yoksa sağ çocuğa ilerle. Bir yaprağa gelmeden dur.
- Tüm yapraklar, soldan sağa.
- Sağ sınır, aşağıdan yukarıya: kökün sağ çocuğundan başlayan sol sınırın aynadaki karşılığı.
Hiçbir düğüm iki kez listelenmez; bu nedenle tek düğümlü bir ağaçta yalnızca kök bulunur.
Fonksiyon
- rootinteger-array
- ikili ağacı seviye sırasına göre, boş konumlar için -1 kullanarak
- Döndürürinteger-array
- kökten başlayarak saat yönünün tersine sınır değerleri
Kısıtlar
1 ≤ root.length ≤ 32767- Her
root[i],-1ya da0 ≤ root[i] ≤ 105koşulunu sağlayan bir değerdir. root[0]hiçbir zaman-1değildir, dolayısıyla ağaçta en az bir düğüm vardır.- Dizi, son düğümden sonra fazladan
-1öğeleriyle bitebilir. - Boş bir noktanın iki çocuğu da boştur ve derinlik en fazla
14'tür. - Düğüm değerleri birbirinden farklıdır.
Örnekler
- Girdi
- root = [7, 3, 9, 1, 5, 8, -1, -1, -1, 4, 6]
- Çıktı
- [7, 3, 1, 4, 6, 8, 9]
- Açıklama
- Kök
7'den sonra sol sınır3'tür: onun çocuğu olan1bir yaprak düğümdür. Yaprak düğümler1,4,6,8'dir. Sağ sınır9'dur;8yaprak düğümünün üzerindedir.
- Girdi
- root = [10, 4, -1, -1, 6, -1, -1, -1, -1, 5, 8]
- Çıktı
- [10, 4, 6, 5, 8]
- Açıklama
4öğesinin sol çocuğu yoktur, bu nedenle sol sınır6'ya döner, ardından yaprak5'te durur.5,8yaprakları takip eder. Kökün sağ çocuğu yoktur.
- Girdi
- root = [3]
- Çıktı
- [3]
- Açıklama
- Kök, ağacın tamamıdır. Bir kez listelenir, yaprak olarak tekrar listelenmez.
Ek soru
Sınırı saat yönünde nasıl listelersiniz: kök, yukarıdan aşağıya sağ kenar, sağdan sola yapraklar, ardından aşağıdan yukarıya sol kenar?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Yanıtı dört parçaya ayır: kök, sol kenar, yapraklar, sağ kenar. Bunlardan hangileri ağaçta aşağı doğru tek bir yol oluşturuyor, hangileri ağacın tamamının dolaşılmasını gerektiriyor?
Her kenar bir yoldur: kökün çocuğundan başlayarak o taraftaki çocuğa, o taraf boşsa diğer çocuğa doğru ilerlemeye devam edin. Soldan sağa sıralı yapraklar, önce sol alt ağacı ziyaret eden derinlik öncelikli bir dolaşım sonucunda elde edilir. Birleşme noktalarına dikkat edin: bir kenarın sona erdiği yaprak da yapraklara dahildir.
1indeksinden aşağı doğru ilerleyin ve her yaprak olmayan düğümü ekleyin. Ardından öncelikli sıralı bir dolaşmayla her yaprak düğümü ekleyin. Sonra2indeksinden aşağı doğru ilerleyin, her yaprak olmayan düğümü toplayın ve bu listeyi ters sırada ekleyin.
Çözüm
Yanıt dört parçayı birleştirir: kök, sol kenar boyunca aşağı inen bir yol, soldan sağa yapraklar ve tersten okunan sağ kenar boyunca aşağı inen bir yol. Birleşme noktalarında, bir kenarı sonlandıran yaprak ve yaprak olan bir kök, her biri yalnızca bir kez listelenmelidir.
Üç bölümü ayrı ayrı incele
Sezgi
Her kenar tek bir yolu izler: kökün çocuğundan başlayıp sıradaki düğüm yaprak olacak noktaya kadar düğümleri listele; yaprak kısmı bunun yerine yaprağı listeler. Soldan sağa önce sol alt ağacı ziyaret eden bir öncelik sıralı dolaşım, yapraklara soldan sağa sırayla ulaşır; çünkü derinliği ne olursa olsun sol alt ağaçtaki her düğüm, sağ alt ağaçtaki düğümlerin solunda yer alır. Sağ kenarı yukarıdan aşağıya topla ve ters çevirip sona ekle.
Kenarlar ayrı ayrı tek bir yolu izler ve yaprak dolaşımı her düğümü bir kez ziyaret eder: O(n) zaman, özyineleme ise h seviye derinliğindedir.
Algoritma
- Kökten başla; eğer bir yapraksa onu döndür.
1indeksinden başlayarak, düğüm var olduğu ve yaprak olmadığı sürece onu ekle ve sol çocuğuna, sol çocuk yoksa sağ çocuğuna geç.1ve2indekslerinden başlayarak, önce solu ziyaret ederek ön-sıralı dolaş ve her yaprağı ekle.2indeksinden başlayarak, sağ çocukları tercih ederek 2. adımdakini yap ve düğümleri topla.- Toplanan düğümleri ters sırada ekle.
def boundaryTraversal(root):
n = len(root)
def real(i):
return i < n and root[i] != -1
def is_leaf(i):
return not real(2 * i + 1) and not real(2 * i + 2)
result = [root[0]]
if is_leaf(0):
return result
# 1. The left boundary, top-down, stopping before its leaf.
i = 1
while real(i) and not is_leaf(i):
result.append(root[i])
i = 2 * i + 1 if real(2 * i + 1) else 2 * i + 2
# 2. Every leaf: a pre-order walk meets them from left to right.
def add_leaves(i):
if not real(i):
return
if is_leaf(i):
result.append(root[i])
return
add_leaves(2 * i + 1)
add_leaves(2 * i + 2)
add_leaves(1)
add_leaves(2)
# 3. The right boundary, collected top-down and added bottom-up.
right = []
i = 2
while real(i) and not is_leaf(i):
right.append(root[i])
i = 2 * i + 2 if real(2 * i + 2) else 2 * i + 1
result.extend(reversed(right))
return resultkenar bayraklarıyla tek bir ön sıralı geçiş
Sezgi
Her düğüme bir bayrak vererek dolaşımları yığın üzerinde tek bir ön sıralı geçişte birleştirin: sol kenarda 1, sağ kenarda 2, içeride 0. Kökün çocukları 1 ve 2 ile başlar. Kenar düğümü, bayrağını kendi tarafındaki çocuğa veya tek çocuğuna aktarır; diğer her çocuk 0 alır. İkinci örnekte 1, 4'ten 6'ya, oradan da 5'e aktarılır.
Düğümler yığından çıktıkça her yaprak düğümü ve 1 bayrağı taşıyan yaprak olmayan her düğümü ekleyin; 2 bayrağı taşıyan yaprak olmayan düğümleri toplayın ve sonunda ters sırayla ekleyin. Ön sıralı dolaşım, tüm sol kenar düğümlerine herhangi bir yapraktan önce ulaşır; çünkü kenar yalnızca solunda hiçbir şey olmayan yerde sağa döner.
Algoritma
- Kökten başlayın. Sağ çocuğunu
2bayrağıyla, ardından sol çocuğunu1bayrağıyla yığına ekleyin. - Bir düğümü yığından çıkarın. Yapraksa veya
1bayrağı varsa ekleyin;2bayrağı olan yaprak olmayan bir düğümü sağ listeye ekleyin. - Sağ çocuğunu, ardından sol çocuğunu, her birini kuralın verdiği bayrakla yığına ekleyin.
- Yığın boşaldığında sağ listeyi tersine çevirip ekleyin.
def boundaryTraversal(root):
n = len(root)
def real(i):
return i < n and root[i] != -1
result = [root[0]]
right = [] # the right boundary, top-down; it goes on the end reversed
# Each entry is (index, edge): 1 = left boundary, 2 = right boundary, 0 = inside.
stack = []
if real(2):
stack.append((2, 2))
if real(1):
stack.append((1, 1))
while stack:
i, edge = stack.pop()
has_left, has_right = real(2 * i + 1), real(2 * i + 2)
if not has_left and not has_right:
result.append(root[i]) # a leaf; pre-order meets them left to right
elif edge == 1:
result.append(root[i]) # the left boundary, top-down
elif edge == 2:
right.append(root[i])
# An edge passes to the child on its own side, or to an only child.
# The right child goes on the stack first, so the left one comes out first.
if has_right:
stack.append((2 * i + 2, edge if edge == 2 or not has_left else 0))
if has_left:
stack.append((2 * i + 1, edge if edge == 1 or not has_right else 0))
result.extend(reversed(right))
return result
Tuzaklar ve uç durumlar
- Bir düğümü iki kez listelemek. Yaprak düğümüne ulaşmadan durmayan bir kenar dolaşımı, 1. örnekte
1değerini iki kez listeler ve tek düğümlü bir ağaçta kök, yaprak olarak yeniden listelenmemelidir. - Her seviyenin ilk düğümünü sol sınır olarak almak. Kökün sol çocuğu yapraksa ve sağ alt ağaç daha derinse, daha derin seviyeler sağ alt ağaçtaki düğümlerle başlar; ancak sol sınır boştur.
- Yalnızca sol çocukları izlemek. 2. örnekte sınır,
4düğümünden sağ çocuğu6düğümüne ilerlemelidir. - Yaprakları seviyelere göre toplamak. Bu durumda 1. örnekte sırasıyla
1,8,4,6elde edilir. - Lua ve R'de,
2i+1aritmetiği için düğüm dizinlerini 0 tabanlı tutun veroot[i + 1]ifadesini okuyun.
Sıkça sorulan sorular3
İkili ağacın sınır dolaşımı nedir?
Ağacın dış sınırını saat yönünün tersine sıralar: kök, yukarıdan aşağıya sol kenar, soldan sağa yapraklar ve aşağıdan yukarıya sağ kenar. Kenarlara yapraklar dahil edilmez, böylece hiçbir düğüm iki kez görünmez.
Sınır dolaşımının zaman karmaşıklığı nedir?
O(n). İki kenar yürüyüşü birer yolu izler ve yaprak yürüyüşü her düğümü bir kez ziyaret eder. Ek alan, özyineleme veya yığın için O(h) kadardır.
Sol sınır her zaman sol çocukları mı takip eder?
Hayır. Bir sol çocuk varsa ona, yoksa sağ çocuğa geçer: soldan gördüğün en dıştaki yol. Kökün sol çocuğu yoksa sol sınır boştur.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def boundaryTraversal(root):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argüman
root = [7, 3, 9, 1, 5, 8, -1, -1, -1, 4, 6]
Beklenen Çıktı
[7, 3, 1, 4, 6, 8, 9]