İkili ağacı yansıt
Görev tanımı
Problem
Bir yerleşim motoru bir sayfayı ikili bir ağaç olarak saklıyor ve sağdan sola yazılan diller bütün yerleşimin çevrilmesini istiyor. İkili bir ağacın kökü verildiğinde her düğümün sol ve sağ çocuklarının yerini değiştir (swap); böylece ağaç ayna görüntüsüne dönüşsün, sonra kökü döndür. Ağaçta en fazla 100 düğüm var. Örnekler sonucu seviye seviye, soldan sağa okunmuş olarak gösteriyor.
Örnekler
Input: tree = 4, left 2 (children 1 and 3), right 7 (children 6 and 9)
Output: [4, 7, 2, 9, 6, 3, 1]
Neden: 7 artık solda duruyor ve her seviye tersten okunuyor
Input: tree = 2, left 1, right 3
Output: [2, 3, 1]
Input: tree = empty
Output: []
Neden: edge case: çevrilecek bir şey yok
İpuçları
0 / 3
Bütün ağacı çevirmek, her alt ağacı çevirip sonra kökteki iki alt ağacın yerini değiştirmekle aynıdır.
Boş bir ağaç kendisinin aynasıdır; bu da özyinelemeye temel durumunu verir.
Her düğümde node.left ile node.right'ın yerini değiştir, sonra iki çocuğu da yansıt. Her düğüm yer değiştirmesini aldığı sürece yer değiştirmenin ve özyinelemeli çağrıların sırası önemli değil.
- Hedef zaman
- O(n)
- Hedef alan
- O(h)
Kısıtlar
- n ≤ 100 nodes
Çözüm
Bir ağacın aynası, solunda yansıtılmış sağ alt ağaç, sağında da yansıtılmış sol alt ağaç olan köküdür; yani tanım zaten bir özyineleme (recursion). Her çağrı düğümünün iki çocuğunun yerini değiştirir ve ikisine de özyineler; boş bir alt ağaç hemen döner. Her düğümün yeri tam bir kez değişir; zaman O(n), h yüksekliğindeki bir ağaçta özyineleme için alan O(h).
from collections import deque
class T:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def mirror(node):
if node is None:
return None
node.left, node.right = mirror(node.right), mirror(node.left) # swap flipped halves
return node
def levels(root):
out, q = [], deque([root] if root else [])
while q:
node = q.popleft()
out.append(node.val)
q.extend(c for c in (node.left, node.right) if c)
return out
print(levels(mirror(T(4, T(2, T(1), T(3)), T(7, T(6), T(9)))))) # -> [4, 7, 2, 9, 6, 3, 1]
print(levels(mirror(T(2, T(1), T(3))))) # -> [2, 3, 1]
print(levels(mirror(None))) # -> []Kodda değil de fikirde mi takıldın? İkili ağaçlar bunu anlatıyor.