Ayna simetrisi kontrolü
Görev tanımı
Problem
İkili bir ağacın, kökten aşağı dikey bir çizgi geçiyormuş gibi kendisinin ayna görüntüsü olup olmadığına karar ver. O çizginin iki yanında hem şekil hem değerler eşleşmeli. Boş bir ağaç simetrik sayılır.
Örnekler
Input: tree = 1, left 2 with children 3 and 4, right 2 with children 4 and 3
Output: True
Neden: sağ alt ağaç, sol alt ağacın tersten okunmuş hali
Input: tree = 1, left 2 with right child 3, right 2 with right child 3
Output: False
Neden: iki tane 3 aynı tarafta asılı, yani şekil yansıtılmamış
Input: tree = empty
Output: True
Neden: edge case: boş ağaç kendiliğinden simetriktir
İpuçları
0 / 3
Simetri tek bir düğümün özelliği değil, orta çizginin iki yanında birbirine bakan düğüm çiftlerinin özelliği.
Bariz olandan farklı bir soru sor: bu ağaç simetrik mi yerine bu iki alt ağaç birbirinin ayna görüntüsü mü diye sor.
Kökün sol ve sağ alt ağaçlarını bir çift olarak karşılaştır. İki alt ağaç, ikisi de yoksa ya da ikisi de eşit değerlerle varsa ve birinin sol çocuğu diğerinin sağ çocuğunu, iki yönde de yansıtıyorsa birbirini yansıtır.
- Hedef zaman
- O(n)
- Hedef alan
- O(h)
Kısıtlar
- the tree may be empty
Çözüm
Doğal özyineleme (recursion) tek düğümler üzerinde değil, çiftler üzerindedir: iki alt ağaç, kökleri uyuştuğunda ve çocukları çapraz olarak, dıştaki dıştakiyle, içteki içtekiyle, birbirini yansıttığında ayna görüntüsüdür. Temel durum (base case), bir eşleşme olan ikisinin de yokluğunu bir şekil uyuşmazlığı olan birinin yokluğundan ayırmalıdır; bir kimlik karşılaştırması ikisini birden kapsar. Her düğüm bir kez ziyaret edilir. Zaman O(n), call stack için alan O(h).
class T:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def is_symmetric(root):
def mirrors(a, b):
if a is None or b is None:
return a is b # true only when both are absent
# outer child against outer child, inner child against inner child
return (a.val == b.val and mirrors(a.left, b.right)
and mirrors(a.right, b.left))
return root is None or mirrors(root.left, root.right)
print(is_symmetric(T(1, T(2, T(3), T(4)), T(2, T(4), T(3))))) # -> True
print(is_symmetric(T(1, T(2, None, T(3)), T(2, None, T(3))))) # -> False
print(is_symmetric(None)) # -> TrueKodda değil de fikirde mi takıldın? İkili ağaçlar bunu anlatıyor.