Symmetric Tree

Q: Simetrik Ağacın zaman karmaşıklığı nedir?

Her gerçek düğüm, eşleştirilmiş bir çiftin parçası olarak bir kez karşılaştırılır; bu nedenle zaman karmaşıklığı O(n) olur. Özyinelemeli ve yığın kullanan sürümler, geçerli yol boyunca bekleyen çiftler için O(h) ek alan kullanır. Seviye seviye ilerleyen sürüm, bir seviyeyi bellekte tutar; en geniş seviye için O(w) alan kullanır.

Q: İkili bir ağacın simetrik olup olmadığını özyineleme kullanmadan nasıl kontrol edersiniz?

Birbirinin aynısı olması gereken düğüm çiftlerinden oluşan bir yığın veya kuyruk tutun; kökün iki çocuğuyla başlayın. Bir çifti çıkarın, eşleşmiyorlarsa başarısız olun ve çocuklarının dıştaki çiftini ve içteki çiftini ekleyin. Yığında uyuşmazlık bulunmadan hiç öğe kalmazsa ağaç simetriktir.

Q: Simetrik bir ağaç ile özdeş iki ağaç arasındaki fark nedir?

İki ağacı, solu solla ve sağı sağla karşılaştırdığınızda özdeşlerse aynıdır. Bir ağaç, sol alt ağacı sağ alt ağacının ayna görüntüsüyle özdeş olduğunda simetriktir; bu nedenle karşılaştırma çapraz yapılır: sol sağla, sağ da solla karşılaştırılır. Aynı çift kontrolü kodu, çocuk çiftlerinin yerleri değiştirilerek her iki problemi de çözer.

KolayAğaç dolaşma

+10

Seviye sırasına göre tree dizisinde saklanan bir ikili ağaç veriliyor. Kök 0 indeksinde bulunur; i indeksindeki düğümün çocukları 2*i+1 (sol) ve 2*i+2 (sağ) indekslerinde bulunur; boş bir konumu -1 belirtir ve dizinin sonunda fazladan -1 girdileri olabilir. Ağaç, kökten geçen dikey bir çizgiye göre kendi ayna görüntüsüyse true, değilse false döndürün. Hem şekil hem de değerler eşleşmelidir.

Fonksiyon

isSymmetric(tree: integer-array) → boolean

treeinteger-array: ikili ağacı seviye sırasına göre, boş konumlar için -1 kullanarak
Döndürürboolean: ağaç kendi ayna görüntüsüyse true, değilse false

Kısıtlar

1 ≤ tree.length ≤ 32767
Her tree[i], -1 ya da 0 ≤ tree[i] ≤ 1000 koşulunu sağlayan bir değerdir.
tree[0] asla -1 değildir, dolayısıyla ağacın en az bir düğümü vardır.
Dizi, son düğümden sonra fazladan -1 girdileriyle bitebilir.
Boş bir noktanın her iki çocuğu da boştur ve derinlik en fazla 14 olur.

Örnekler

Girdi: tree = [1, 2, 2, 3, 4, 4, 3]
Çıktı: true
Açıklama: Ağacı ortadan ikiye katlayın. 1 ve 2 indekslerindeki iki 2 birleşir, 3 ve 6 indekslerindeki dıştaki 3ler birleşir ve 4 ile 5 indekslerindeki içteki 4ler birleşir.

Girdi: tree = [1, 2, 2, -1, 3, -1, 3]
Çıktı: false
Açıklama: Her iki 3 de ebeveynlerinin sağında yer alır. Ayna görüntüsünde, sol 2'nin sağ çocuğu (indeks 4), sağ 2'nin sol çocuğuna (indeks 5) bakmalıdır ve 5 indeksi boştur.

Girdi: tree = [4, 6, 6, 5, -1, -1, 9]
Çıktı: false
Açıklama: Şekil bir ayna görüntüsüdür: 3 indeksi 6 indeksine bakar ve her ikisi de bir düğüm içerir. Değerleri farklıdır: 5 ve 9; dolayısıyla ağaç simetrik değildir.

Ek soru

Şekil kendi içinde yansıyorsa ancak bazı değerler aynı değilse, ağacı simetrik hâle getirmek için en az kaç düğüm değerini değiştirmelisiniz?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Simetri, çiftlerin bir özelliğidir. Her düğümün kökün diğer tarafındaki ayna görüntüsü konumunda bir eşi vardır ve sol çocuğun eşi sağ çocuktur. Bu nedenle bir düğümü hiçbir zaman kendi çocuklarıyla karşılaştırmazsın: ağacın iki yarısında aynı anda zıt yönlerde ilerler, her düğüm çiftinde şekli ve değeri karşılaştırır ve uyuşmayan ilk çiftte durursun.

Tüm seviyeleri tersleriyle karşılaştırın

Sezgi

Önce, dizide nasıl gezinileceğine bakalım. i indeksindeki düğümün sol çocuğu 2*i+1, sağ çocuğu ise 2*i+2 indeksindedir. Bir çocuk yalnızca indeksi dizi sınırları içindeyse ve oradaki değer -1 değilse gerçektir. [1, 2, 2, 3, 4, 4, 3] dizisinde kök 1'in çocukları 1 ve 2 indekslerinde, 1 indeksindeki 2'nin çocukları ise 3 ve 4 indekslerindedir.

Şimdi ağaca her seferinde bir düzey olacak şekilde bakalım. Ayna görüntüsü soldan sağa ve sağdan sola aynı okunduğundan, boş yerleri de dahil ederek yazılan her düzey iki yönde de aynı okunmalıdır. İlk örnekte kökün altındaki düzeyler 2 2 ve 3 4 4 3 şeklindedir. İkinci örnekte ise 2 2 ve ardından -1 3 -1 3 okunur; bunun tersi 3 -1 3 -1 olduğundan yanıt false olur.

Boş yerler satırda kalmalıdır. Bunlar olmadan ikinci örneğin en alt düzeyi 3 3 okunur ve testten geçerdi. Düzeydeki her gerçek düğümün her çocuk yeri için bir girdi yazın; boş olanlar için -1 kullanın. Boş yerlerin çocukları da boştur, dolayısıyla bunlar hiçbir şey eklemez. Her düğüm bir kez ziyaret edilir; bu nedenle zaman karmaşıklığı O(n), bellekte aynı anda tutulan tek bir düzeyin alan karmaşıklığı ise en geniş düzeyin genişliği w için O(w) olur.

Algoritma

Kök indeksini 0 içeren bir listeyle başlayın.
Listedeki her indeks için soldan sağa, her iki çocuk konumunu da yazın: çocuk gerçekse değerini, boşsa -1 yazın. Bir sonraki seviye için gerçek çocukları toplayın.
Çocuk konumlarının bulunduğu bu satır tersiyle farklıysa false döndürün.
Sonraki seviyeye geçin ve boş olana kadar tekrarlayın, ardından true döndürün.

def isSymmetric(tree):
    n = len(tree)
    level = [0]  # the real nodes of one level, left to right
    while level:
        row = []  # the child spots under this level, -1 for an empty one
        next_level = []
        for i in level:
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and tree[child] != -1:
                    row.append(tree[child])
                    next_level.append(child)
                else:
                    row.append(-1)
        if row != row[::-1]:
            return False
        level = next_level
    return True

Yansıtılmış çiftler üzerinde özyineleme

Sezgi

Tüm seviyeleri karşılaştırmak yerine iki alt ağacı karşılaştırın: 1 dizininden başlayan kökün sol alt ağacını ve 2 dizininden başlayan sağ alt ağacını. İki konum, ikisi de boş olduğunda veya ikisi de aynı değeri taşıyıp çocukları çapraz eşleştiğinde birbirinin aynasıdır. Birinin sol çocuğu diğerinin sağ çocuğunun aynasıdır (dış çift) ve birinin sağ çocuğu diğerinin sol çocuğunun aynasıdır (iç çift).

İlk örnekte mirrors(1, 2) iki 2 değerini karşılaştırır, ardından dıştaki 3 değerleri için mirrors(3, 6), içteki 4 değerleri için de mirrors(4, 5) çağrılarını yapar. Bunların her biri aşağıda yalnızca boş konumlar bulur ve true döndürür. İkinci örnekte mirrors(4, 5), 4 dizininde bir 3 ile karşısındaki 5 dizininde boş bir konum bulur, false döndürür ve false en üste kadar geri çıkar.

Her gerçek düğüm en fazla bir çifte ait olduğundan, zaman karmaşıklığı O(n)'dir. Çağrı yığınının derinliği ağacın yüksekliği kadardır; yani O(h)'dir ve burada en fazla 14 çerçevedir.

Algoritma

mirrors(a, b) yazın. Bir konum, indeksi dizinin sonunu aşıyorsa veya -1 değerini içeriyorsa boştur. Her iki konum da boşsa true döndürün; yalnızca biri boşsa false döndürün.
tree[a] ile tree[b] farklıysa false döndürün.
Aksi takdirde mirrors(2*a+1, 2*b+2) ve mirrors(2*a+2, 2*b+1) sonuçlarını döndürün.
mirrors(1, 2) sonucunu döndürün. Çocuğu olmayan bir kök, iki boş konum verir; bu da true değeridir.

def isSymmetric(tree):
    n = len(tree)

    def mirrors(a, b):
        # Spots a and b must hold the same value, or both be empty.
        empty_a = a >= n or tree[a] == -1
        empty_b = b >= n or tree[b] == -1
        if empty_a or empty_b:
            return empty_a and empty_b
        return (tree[a] == tree[b]
                and mirrors(2 * a + 1, 2 * b + 2)   # outer pair
                and mirrors(2 * a + 2, 2 * b + 1))  # inner pair

    return mirrors(1, 2)

Aynalanmış çiftlerden oluşan açık yığın

Sezgi

Özyineleme yalnızca tek bir şeye ihtiyaç duyar: hâlâ kontrol edilmeyi bekleyen çiftlere. Bu çiftleri kendi yığınınızda tutun; böylece çağrılar ortadan kalkar. (1, 2) çiftiyle başlayın. Bir çifti çıkarın. Her iki konum da boşsa, altlarında incelenecek bir şey yoktur; devam edin. Konumlardan biri boşsa veya değerler farklıysa ağaç simetrik değildir. Aksi hâlde dış çifti (2*a+1, 2*b+2) ve iç çifti (2*a+2, 2*b+1) yığına ekleyin.

Çiftleri kontrol etme sıranız önemli değildir; çünkü ağaç ancak her çift eşleşirse simetriktir. Yığın derinlik öncelikli sıra sağlar; kuyruk ise seviye sırası sağlar ve aynı şekilde çalışır. Üçüncü örnek, ilk hatalı çift olan (3, 6) noktasında durur; bu çift 5 ve 9 değerlerini içerir.

Her çıkarma işlemi bir çifti işler ve her gerçek düğüm en fazla bir çiftte yer alır; bu nedenle zaman karmaşıklığı O(n)'dir. Yığın, geçerli yolun her seviyesi için yaklaşık bir bekleyen çift tutar; alan karmaşıklığı O(h)'dir ve endişelenmeniz gereken bir özyineleme sınırı yoktur.

Algoritma

(1, 2) çiftini bir yığına ekle.
(a, b) çiftini çıkar. Her iki konum da boşsa (indeks sonu geçmişse veya -1 ise), sonraki çifte geç.
Yalnızca bir konum boşsa veya tree[a], tree[b]'den farklıysa false döndür.
(2*a+1, 2*b+2) ve (2*a+2, 2*b+1) değerlerini ekle.
Yığın boşaldığında true döndür.

def isSymmetric(tree):
    n = len(tree)
    stack = [(1, 2)]  # pairs of spots that must mirror each other
    while stack:
        a, b = stack.pop()
        empty_a = a >= n or tree[a] == -1
        empty_b = b >= n or tree[b] == -1
        if empty_a and empty_b:
            continue
        if empty_a or empty_b or tree[a] != tree[b]:
            return False
        stack.append((2 * a + 1, 2 * b + 2))  # outer pair
        stack.append((2 * a + 2, 2 * b + 1))  # inner pair
    return True

Tuzaklar ve uç durumlar

Yanlış yanıtların çoğu yanlış düğüm çiftini karşılaştırır veya boş bir yerin şeklin bir parçası olduğunu unutur.

Her alt ağacı kendi başına kontrol etmek. Sol alt ağacın kendi başına simetrik olması gerekmez: [1, 2, 2, 3, 4, 4, 3] içinde 2, 3, 4 alt ağacı simetrik değildir, ancak ağacın tamamı simetriktir. Sol alt ağacın sağ alt ağacı yansıtması gerekir.
Çocukları yanlış biçimde eşleştirmek. Bir tarafın sol çocuğu, diğer tarafın sağ çocuğuna denk gelir: (2*a+1, 2*b+2) ve (2*a+2, 2*b+1); asla (2*a+1, 2*b+1) değil.
Yalnızca değerleri karşılaştırmak. [1, 2, 2, -1, 3, -1, 3] içindeki boş yerleri kaldırırsanız her seviye iki yönde de aynı görünür, ancak ağaç simetrik değildir. Seviye satırında -1 değerini koruyun veya çift kontrolünde boş olup olmadığını denetleyin.
Dizinin sonunu aşacak şekilde okumak. Dizinin sonrasındaki bir indeks boş bir yerdir. tree[a] değerini okumadan önce a < n kontrolünü yapın; tek düğümlü bir ağacın 1 veya 2 indeksi hiç yoktur.
İlk eşleşen çiftte durmak. Tek bir iyi çift hiçbir şeyi kanıtlamaz; yalnızca tüm çiftler kontrol edildikten sonra true döndürün.
Dizilerin 1'den başladığı Lua ve R dillerinde ofseti karıştırmak. 2*i+1 hesabı için düğüm indekslerini 0 tabanlı tutun ve tree[i + 1] değerini okuyun.

Sıkça sorulan sorular3

Simetrik Ağacın zaman karmaşıklığı nedir?

Her gerçek düğüm, eşleştirilmiş bir çiftin parçası olarak bir kez karşılaştırılır; bu nedenle zaman karmaşıklığı O(n) olur. Özyinelemeli ve yığın kullanan sürümler, geçerli yol boyunca bekleyen çiftler için O(h) ek alan kullanır. Seviye seviye ilerleyen sürüm, bir seviyeyi bellekte tutar; en geniş seviye için O(w) alan kullanır.

İkili bir ağacın simetrik olup olmadığını özyineleme kullanmadan nasıl kontrol edersiniz?

Birbirinin aynısı olması gereken düğüm çiftlerinden oluşan bir yığın veya kuyruk tutun; kökün iki çocuğuyla başlayın. Bir çifti çıkarın, eşleşmiyorlarsa başarısız olun ve çocuklarının dıştaki çiftini ve içteki çiftini ekleyin. Yığında uyuşmazlık bulunmadan hiç öğe kalmazsa ağaç simetriktir.

Simetrik bir ağaç ile özdeş iki ağaç arasındaki fark nedir?

İki ağacı, solu solla ve sağı sağla karşılaştırdığınızda özdeşlerse aynıdır. Bir ağaç, sol alt ağacı sağ alt ağacının ayna görüntüsüyle özdeş olduğunda simetriktir; bu nedenle karşılaştırma çapraz yapılır: sol sağla, sağ da solla karşılaştırılır. Aynı çift kontrolü kodu, çocuk çiftlerinin yerleri değiştirilerek her iki problemi de çözer.

def isSymmetric(tree):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argüman

tree = [1, 2, 2, 3, 4, 4, 3]

Beklenen Çıktı

true

Symmetric Tree

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Tüm seviyeleri tersleriyle karşılaştırın

Yansıtılmış çiftler üzerinde özyineleme

Aynalanmış çiftlerden oluşan açık yığın

Tuzaklar ve uç durumlar

Sıkça sorulan sorular3

Benzer problemler