Subtree of Another Tree

Q: Başka Bir Ağacın Alt Ağacının zaman karmaşıklığı nedir?

Her düğümden karşılaştırma yapmak, en kötü durumda O(n·m) maliyetlidir; burada n ve m iki ağacın boyutlarıdır. Yalnızca yüksekliği subRoot yüksekliğine eşit olan düğümlerde karşılaştırma yapmak, bunu O(n + m) düzeyine indirir; çünkü root içindeki her düğüm en fazla bir kez dolaşılır.

Q: Bir Ağaç Alt Ağacı, dize eşleştirme kullanılarak çözülebilir mi?

Evet. Her ağacı, her boş çocuk için # kullanarak ve her değerden önce bir ayraç koyarak öncelikli sıralamada yaz: ,2,1,#,#,3,#,# . subRoot , dizesi root dizesinin içinde geçtiğinde tam olarak bir alt ağaçtır ve KMP bunu O(n + m) sürede bulur. İşaretçiler olmadan farklı şekiller aynı dizeyi verir; ayraçlar olmadan 12 , 2 içerir.

KolayAğaç dolaşma Özyineleme

+10

İki ikili ağaç veriliyor: root ve subRoot. Her biri, seviye sırasına göre bir dizide saklanıyor: kök 0 indeksinde, i indeksindeki düğümün çocukları 2*i+1 (sol) ve 2*i+2 (sağ) indekslerinde yer alıyor; boş bir konum için -1 kullanılıyor. Bir dizinin sonunda fazladan -1 girdileri bulunabilir.

root içindeki herhangi bir düğümün, tüm alt düğümleriyle birlikte, şekli ve değerleri subRoot ile tam olarak aynıysa true, aksi hâlde false döndürün. root ağacının tamamı da sayılır.

Fonksiyon

isSubtree(root: integer-array, subRoot: integer-array) → boolean

rootinteger-array: aranacak ağaç, boş konumlar için -1 kullanılarak seviye sırasına göre
subRootinteger-array: aranacak ağaç, aynı biçimde
Döndürürboolean: true, subRoot root içinde tüm alt öğeleriyle birlikte bir düğüm olarak bulunuyorsa; aksi hâlde false

Kısıtlar

1 ≤ root.length ≤ 32767 ve 1 ≤ subRoot.length ≤ 32767
Her giriş -1 ya da 0 ile 10⁴ arasında bir değerdir.
root[0] ve subRoot[0] hiçbir zaman -1 değildir, dolayısıyla her iki ağaçta da en az bir düğüm vardır.
Her iki diziden herhangi biri, son düğümünden sonra fazladan -1 girdileriyle bitebilir.
Boş bir noktanın her iki çocuğu da boştur ve her ağacın derinliği en fazla 14 olur.
Değerler tekrarlanabilir.

Örnekler

Girdi: root = [6, 2, 8, 1, 3, -1, 9]subRoot = [2, 1, 3]
Çıktı: true
Açıklama: 1 indeksindeki 2 düğümünün çocukları 1 ve 3'tür ve ikisi de yapraktır. Bu tam olarak subRoot'tur.

Girdi: root = [6, 2, 8, 1, 3, -1, 9, -1, -1, 0]subRoot = [2, 1, 3]
Çıktı: false
Açıklama: 2 düğümünün altındaki 3 artık 0 adlı bir çocuğa sahip. Bir alt ağaç tüm torun düğümleri içerir; bu nedenle 2 düğümü, subRoot içindeki üç düğüme karşılık dört düğüm içerir ve başka hiçbir düğüm 2 değerini taşımaz.

Girdi: root = [5, 5, 7]subRoot = [5]
Çıktı: true
Açıklama: Kök 5'in iki çocuğu vardır, bu nedenle tek düğüm 5 ile eşleşmez. 1 indeksindeki 5 bir yaprak düğümdür ve eşleşir.

Ek soru

Her alt ağacı değerinden ve çocuklarının parmak izlerinden yola çıkarak parmak iziyle tanımlayabilir misin, böylece subRoot ile karşılaştırma O(1) maliyetli olur? İki farklı alt ağaç çakıştığında ne yaparsın?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Problemin iki bölümü vardır: iki ağacın özdeş olup olmadığına karar vermek ve bu kontrolü root içinde nerede yapacağını seçmek. Yalnızca yüksekliği subRoot yüksekliğine eşit olan bir düğüm eşleşebilir ve aynı yükseklikteki düğümler hiçbir zaman iç içe geçmez; bu nedenle yalnızca bunları kontrol etmek, root içindeki her düğüm üzerinde en fazla bir kez gezinir.

Her düğümde karşılaştır

Sezgi

i konumu, dizi içinde olduğunda ve o konumdaki değer -1 olmadığında geçerlidir. İki ağaç, ikisi de boşsa veya kökleri aynı değeri taşıyor ve sol alt ağaçları ile sağ alt ağaçları özdeşse özdeştir. same(i, j), root ağacında i konumundan ve subRoot ağacında j konumundan aynı anda ilerler. subRoot, root içinde görünüyorsa kökü bir düğümde yer alır; bu nedenle her geçerli i konumundan same(i, 0) çağrısını deneyin.

Yakın bir eşleşme, başarısız olmadan önce n düğümün her birinde en fazla m adım sürebilir: O(n·m). Burada derinlik sınırı bunu kısıtlar: bir düğüm, yalnızca o düğümde veya onun üstünde başlayan kontroller tarafından, en fazla 14 kez dolaşılır.

Algoritma

same(i, j) fonksiyonunu yaz. root içindeki i konumu ile subRoot içindeki j konumu ikisi de boşsa true döndür; yalnızca biri boşsa false döndür.
İki değer farklıysa false döndür. Aksi hâlde same(2*i+1, 2*j+1) ve same(2*i+2, 2*j+2) döndür.
root içindeki geçerli bir i indeksi için same(i, 0) koşulu sağlanıyorsa true, aksi hâlde false döndür.

def isSubtree(root, subRoot):
    n, m = len(root), len(subRoot)

    def same(i, j):
        # True if the subtree at root[i] equals the subtree at subRoot[j].
        a = i < n and root[i] != -1
        b = j < m and subRoot[j] != -1
        if not a or not b:
            return a == b  # two empty spots match, one empty spot does not
        if root[i] != subRoot[j]:
            return False
        return same(2 * i + 1, 2 * j + 1) and same(2 * i + 2, 2 * j + 2)

    # Try every real node of root as the top of a match.
    for i in range(n):
        if root[i] != -1 and same(i, 0):
            return True
    return False

Yalnızca yükseklikler eşleştiğinde karşılaştırın

Sezgi

Özdeş ağaçların yüksekliği aynıdır; bu yükseklik, aşağı doğru en uzun yoldaki düğümlerin sayısı olarak hesaplanır. Bu nedenle yalnızca yüksekliği subRoot yüksekliğine eşit olan root düğümlerini kontrol etmeye değer. İlk örnekte subRoot yüksekliği 2 ve root içinde yalnızca 2 ve 8 bu yüksekliğe sahip.

Bir düğüm, altındaki tüm düğümlerden daha yüksektir; bu nedenle eşit yüksekliğe sahip iki düğümden biri diğerinin içinde yer almaz. Her kontrol yalnızca başlangıç düğümünün alt ağacında dolaşır; dolayısıyla kontroller birlikte root içindeki her düğümü en fazla bir kez ziyaret eder.

Çocuklar, ebeveynlerinden daha büyük indekslerde yer alır; bu nedenle son indeksten başlayan bir tarama her iki çocuğa da ebeveynden önce ulaşır. İki yükseklik taraması ve kontroller O(n + m) zaman alır.

Algoritma

Her ağaç için, son indeksten başlayıp 0 değerine kadar geriye doğru tarayarak bir yükseklik dizisi doldurun: boş bir konum 0 alır, gerçek bir düğüm ise iki çocuğunun yüksekliklerinden büyük olana 1 eklenmiş değeri alır.
root dizisinin, yüksekliği subRoot dizisinin 0 indeksindeki yüksekliğe eşit olan her i indeksi için same(i, 0) çalıştırın ve koşul sağlanıyorsa true döndürün.
false döndürün.

def isSubtree(root, subRoot):
    n, m = len(root), len(subRoot)

    def same(i, j):
        # True if the subtree at root[i] equals the subtree at subRoot[j].
        a = i < n and root[i] != -1
        b = j < m and subRoot[j] != -1
        if not a or not b:
            return a == b  # two empty spots match, one empty spot does not
        if root[i] != subRoot[j]:
            return False
        return same(2 * i + 1, 2 * j + 1) and same(2 * i + 2, 2 * j + 2)

    def heights(tree):
        # Children sit at larger indexes, so a backward scan finishes them first.
        h = [0] * len(tree)
        for i in range(len(tree) - 1, -1, -1):
            if tree[i] != -1:
                left = h[2 * i + 1] if 2 * i + 1 < len(tree) else 0
                right = h[2 * i + 2] if 2 * i + 2 < len(tree) else 0
                h[i] = 1 + max(left, right)
        return h

    target = heights(subRoot)[0]
    rootHeights = heights(root)
    # Only a node of the same height can match, and no two such nodes overlap.
    for i in range(n):
        if rootHeights[i] == target and same(i, 0):
            return True
    return False

Tuzaklar ve uç durumlar

İkinci örnekte olduğu gibi kısmi bir eşleşmeyi kabul etmek. root içinde bir düğüm varken subRoot boş bir konuma sahipse same başarısız olmalıdır.
Doğru değere sahip ilk düğümde durmak. Üçüncü örnekte kökteki 5 eşleşmez, onun altındaki yaprak 5 ise eşleşir.
İki dizinin dilimlerini karşılaştırmak. Bir alt ağacın düğümleri birçok seviyeye yayılır ve dizilerden herhangi biri fazladan -1 öğeleriyle bitebilir. Sınırın ötesindeki bir indeks, -1 gibi boş bir konumdur.
Lua ve R'de, 2*i+1 aritmetiği için düğüm indekslerini 0 tabanlı tutun ve root[i + 1] okuyun.

Sıkça sorulan sorular3

Başka Bir Ağacın Alt Ağacının zaman karmaşıklığı nedir?

Her düğümden karşılaştırma yapmak, en kötü durumda O(n·m) maliyetlidir; burada n ve m iki ağacın boyutlarıdır. Yalnızca yüksekliği subRoot yüksekliğine eşit olan düğümlerde karşılaştırma yapmak, bunu O(n + m) düzeyine indirir; çünkü root içindeki her düğüm en fazla bir kez dolaşılır.

Bir Ağaç Alt Ağacı, dize eşleştirme kullanılarak çözülebilir mi?

Evet. Her ağacı, her boş çocuk için # kullanarak ve her değerden önce bir ayraç koyarak öncelikli sıralamada yaz: ,2,1,#,#,3,#,#. subRoot, dizesi root dizesinin içinde geçtiğinde tam olarak bir alt ağaçtır ve KMP bunu O(n + m) sürede bulur. İşaretçiler olmadan farklı şekiller aynı dizeyi verir; ayraçlar olmadan 12, 2 içerir.

subRoot ile eşleşen ancak fazladan çocukları olan bir düğüm sayılır mı?

Hayır. Bir alt ağaç, bir düğüm ve tüm alt düğümlerinden oluşur; bu nedenle eşleşmenin altındaki her düğüm subRoot içinde de yer almalıdır. İkinci örnekte 3 altındaki fazladan 0, yanıtı false yapar.

def isSubtree(root, subRoot):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argümanlar

root = [6, 2, 8, 1, 3, -1, 9]
subRoot = [2, 1, 3]

Beklenen Çıktı

true