Construct Binary Tree from Preorder and Inorder Traversal

Q: İkili bir ağacı yeniden oluşturmak için neden hem preorder hem de inorder gerekir?

Yalnızca preorder, şekli belirlemez. [1, 2] preorder dizisi, 2 ’nin 1 ’in sol çocuğu olduğu bir ağaca da sağ çocuğu olduğu bir ağaca da uyar. Inorder bunu netleştirir: [2, 1] , 2 ’yi sola; [1, 2] ise sağa yerleştirir. Değerler birbirinden farklı olduğunda, bu ikili tam olarak bir ağacı tanımlar.

Q: Bir ikili ağacı preorder ve postorder dolaşım sıralarından yeniden oluşturabilir misin?

Genel olarak hayır. Preorder [1, 2] ve postorder [2, 1] , hem sol çocuk hem de sağ çocuk durumuyla uyumludur; çünkü bu dolaşımların hiçbirinde kök, alt ağaçlarının arasında yer almaz. Bu ikili yalnızca her düğümün sıfır ya da iki çocuğu olduğu tam ikili ağaçlar için yeterlidir.

OrtaAğaç dolaşma Hashing Özyineleme

+10

Size aynı ikili ağacın farklı değerlerini listeleyen iki dizi, preorder ve inorder, veriliyor. Preorder dolaşımında önce bir düğüm, sonra sol alt ağacı, ardından sağ alt ağacı ziyaret edilir. Inorder dolaşımında ise önce sol alt ağaç, sonra düğüm, ardından sağ alt ağaç ziyaret edilir.

Ağacı yeniden oluştur ve seviye sırasına göre bir dizi olarak döndür: kök 0 indeksinde, i indeksindeki düğümün çocukları sırasıyla 2i+1 (sol) ve 2i+2 (sağ) indekslerinde, her boş konum için -1 bulunur. Dizi son düğümde biter; sonunda -1 bulunmaz.

Fonksiyon

buildTree(preorder: integer-array, inorder: integer-array) → integer-array

preorderinteger-array: ön sıralı dolaşımdaki değerler: düğüm, sol alt ağaç, sağ alt ağaç
inorderinteger-array: inorder içindeki değerler: sol alt ağaç, düğüm, sağ alt ağaç
Döndürürinteger-array: seviye sırasına göre ağaç; boş yerler için -1 kullanın ve sonda -1 bulunmasın

Kısıtlar

1 ≤ preorder.length ≤ 3000
inorder.length == preorder.length
0 ≤ preorder[i] ≤ 10⁴ ve tüm değerler birbirinden farklıdır.
inorder aynı değerleri tutar ve her iki dizi de aynı ikili ağacı tanımlar.
Ağacın derinliği en fazla 14 olduğundan, cevaptaki her indeks 2¹⁴-1 = 16383 değerinden küçüktür.

Örnekler

Girdi: preorder = [7, 3, 0, 9, 4, 6]inorder = [0, 3, 9, 7, 4, 6]
Çıktı: [7, 3, 4, 0, 9, -1, 6]
Açıklama: Ön sipariş kökle, 7 ile başlar. inorder konumu 3'te bulunur; bu nedenle 0, 3, 9 sola, 4, 6 sağa gider. 4'ün yalnızca 6 adlı bir sağ çocuğu vardır; bu yüzden 5 indeksi -1 olarak kalır.

Girdi: preorder = [1, 2, 3]inorder = [2, 3, 1]
Çıktı: [1, 2, -1, -1, 3]
Açıklama: Kök 1, inorder içinde en sonda gelir, bu nedenle 2 indeksi -1'dir. 2, 3 arasından preorder önce 2'yi listeler ve inorder 3'ü ondan sonra koyar; dolayısıyla 3, 4 indeksinde onun sağ çocuğudur.

Ek soru

Özyineleme kullanmadan, preorder üzerinde tek geçişte ve açık bir yığın kullanarak ağacı yeniden oluşturabilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Önce sıralama, her alt ağacın kökünü verir: uzantısındaki ilk değer. Simetrik sıralama, bölünme noktasını verir: kökten önceki değerler sola, sonraki değerler sağa gider. Her iki yarıda da özyineleme yapmak ağacı yeniden oluşturur ve değerden simetrik sıralamadaki konuma giden bir eşleme, her kök aramasını tek adıma indirir.

Kökü tarayarak özyinelemeli olarak bölün

Sezgi

Preorder sıralamasında sol alt ağaç, kökünü izler ve her değer için bir girdi kullanır; bunların sayısı m-lo'dur. Burada m, kökün inorder konumudur. Sağ alt ağaç ondan sonra gelir; dolayısıyla kökü pre+1+(m-lo) konumundadır. İlk örnekte sol bölüm 0, 3, 9 üç değer içerir; bu nedenle sağ alt ağaç preorder dizininde 4 konumunda, yani 4 değeriyle başlar.

En fazla 14 derinlik, her çıktı dizinini 2^14-1 değerinin altında tutar. Bu kadar hücreyi -1 ile doldurun, her değeri kendi dizinine yazın ve sonunda sondaki -1 girdilerini kesin.

Kökünü bulmak için her inorder aralığını taramak O(n·h) maliyetindedir: aynı düzeydeki aralıklar çakışmadığından bir düzey en fazla n girdi tarar; burada bu, en fazla 14 × 3000 = 42000 adımdır. Derinlik sınırı olmadığında, yol biçimindeki bir ağaç bu maliyeti O(n²) yapar.

Algoritma

out dizisini tümü -1 olan 2^14-1 girdiyle oluşturun.
build(pre, lo, hi, h) yazın: lo > hi ise geri dönün. Aksi takdirde preorder[pre] değerini out[h] konumuna yazın.
Kökün konumu m'yi bulmak için inorder dizisini lo konumundan başlayarak tarayın. Sol alt ağaçta m-lo değer bulunur.
build(pre+1, lo, m-1, 2*h+1) ve build(pre+1+(m-lo), m+1, hi, 2*h+2) çağrılarını yapın.
build(0, 0, n-1, 0) çağrısını yapın, ardından sondaki -1 girdilerini çıkarıp geri kalanını döndürün.

def buildTree(preorder, inorder):
    out = [-1] * (2 ** 14 - 1)  # every index of a depth-14 tree is below 2^14-1

    def build(pre, lo, hi, h):
        # preorder[pre] is the root of the subtree that inorder[lo..hi] lists;
        # it goes to index h of the output.
        if lo > hi:
            return
        value = preorder[pre]
        out[h] = value
        m = lo
        while inorder[m] != value:  # find the root in the inorder range
            m += 1
        left_size = m - lo
        build(pre + 1, lo, m - 1, 2 * h + 1)
        build(pre + 1 + left_size, m + 1, hi, 2 * h + 2)

    build(0, 0, len(inorder) - 1, 0)
    last = len(out) - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

Bir konum haritasıyla özyinelemeli olarak bölme

Sezgi

Değerler birbirinden farklıdır, bu nedenle her birinin inorder içinde tam olarak bir konumu vardır. Özyineleme başlamadan önce bunu değerden konuma eşleme yapan bir haritaya kaydedin; böylece her kök araması tek adımda tamamlanır.

Haritayı oluşturmak O(n) sürer ve her değer daha sonra sabit işlemle bir kez yerleştirilir; dolayısıyla toplam süre O(n) olur. Harita O(n) alan kullanır ve özyineleme her seviye için bir çerçeve kullanır. C ve R'de değerler en fazla 10^4 olduğundan, 10^4+1 öğeli basit bir dizi harita olarak kullanılabilir.

Algoritma

inorder değerlerinin her birini konumuna eşleyen bir harita oluşturun.
Tüm girdileri -1 olan, 2^14-1 elemanlı bir out oluşturun.
build(pre, lo, hi, h) içinde, lo > hi ise geri dönün; aksi takdirde preorder[pre] değerini out[h] konumuna yazın ve haritada bu değerin konumu olan m değerini bulun.
build(pre+1, lo, m-1, 2*h+1) ve build(pre+1+(m-lo), m+1, hi, 2*h+2) ile özyinelemeli çağrılar yapın.
build(0, 0, n-1, 0) çağrısını yapın, ardından sondaki -1 girdilerini çıkarıp geri kalanını döndürün.

def buildTree(preorder, inorder):
    position = {value: i for i, value in enumerate(inorder)}  # value -> inorder index
    out = [-1] * (2 ** 14 - 1)  # every index of a depth-14 tree is below 2^14-1

    def build(pre, lo, hi, h):
        # preorder[pre] is the root of the subtree that inorder[lo..hi] lists;
        # it goes to index h of the output.
        if lo > hi:
            return
        value = preorder[pre]
        out[h] = value
        m = position[value]
        left_size = m - lo
        build(pre + 1, lo, m - 1, 2 * h + 1)
        build(pre + 1 + left_size, m + 1, hi, 2 * h + 2)

    build(0, 0, len(inorder) - 1, 0)
    last = len(out) - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

Tuzaklar ve uç durumlar

Sağ alt ağacın başlangıcını pre+1+(m-lo) yerine pre+1+m olarak belirlemek. En üst çağrıda olduğu gibi lo değeri 0 iken çalışır, ancak aralık daha ileriden başladığında bozulur.
Boşlukları atlamak. Eksik bir çocuk yine de kendi yerini kaplar; bu nedenle ikinci örneğin yanıtı [1, 2, -1, -1, 3] olur, [1, 2, 3] değil.
Sondaki -1 girdilerini bırakmak. 2^14-1 hücrenin tamamını döndürmek, ilk örneğe fazladan 16376 -1 girdisi ekler.
Her çağrıda her iki dizinin de dilimlerini kopyalamak; bu, her seviyeye O(n) maliyet ekler. Dizin aralıklarını parametre olarak aktarın.
Lua ve R'de diziler 1'den başlar. Aritmetik işlemlerde konumları 0 tabanlı tutun ve preorder[pre + 1] ile out[h + 1] öğelerini okuyun.

Sıkça sorulan sorular3

İkili bir ağacı yeniden oluşturmak için neden hem preorder hem de inorder gerekir?

Yalnızca preorder, şekli belirlemez. [1, 2] preorder dizisi, 2’nin 1’in sol çocuğu olduğu bir ağaca da sağ çocuğu olduğu bir ağaca da uyar. Inorder bunu netleştirir: [2, 1], 2’yi sola; [1, 2] ise sağa yerleştirir. Değerler birbirinden farklı olduğunda, bu ikili tam olarak bir ağacı tanımlar.

Ön sıralı ve iç sıralı dolaşımlardan ikili ağaç oluşturmanın zaman karmaşıklığı nedir?

Değerden inorder konumuna bir eşlemeyle, zaman karmaşıklığı O(n) ve ek alan karmaşıklığı O(n) olur. Eşleme olmadan, her inorder aralığını kökünü bulmak için taramak O(n·h) maliyetindedir; bu da yol şeklindeki bir ağaçta O(n²) olur.

Bir ikili ağacı preorder ve postorder dolaşım sıralarından yeniden oluşturabilir misin?

Genel olarak hayır. Preorder [1, 2] ve postorder [2, 1], hem sol çocuk hem de sağ çocuk durumuyla uyumludur; çünkü bu dolaşımların hiçbirinde kök, alt ağaçlarının arasında yer almaz. Bu ikili yalnızca her düğümün sıfır ya da iki çocuğu olduğu tam ikili ağaçlar için yeterlidir.

def buildTree(preorder, inorder):
    # Kodu buraya yazın

Test #1

Test #2

Argümanlar

preorder = [7, 3, 0, 9, 4, 6]
inorder = [0, 3, 9, 7, 4, 6]

Beklenen Çıktı

[7, 3, 4, 0, 9, -1, 6]