Düğüm, sol, sağ

İkili ağaç düğümlerden oluşur; her düğümün bir değeri ve en çok iki çocuğu vardır: sol ve sağ. En üstteki düğüme kök, çocuğu olmayanlara yaprak denir. Önemli olan şudur: bir düğümün solu da sağı da kendi başına birer ağaçtır. Bu yüzden ağaç soruları özyinelemeye çok yakışır.

1def total(node):
2    if node is None:
3        return 0
4    return node.val + total(node.left) + total(node.right)

Kalıp neredeyse hiç değişmez: boş ağacın cevabı nedir (taban durumu), ve bir düğümün cevabı, iki çocuğunun cevabından nasıl çıkar? Toplam için: boş ağaç 0, düğüm ise kendi değeri artı iki alt ağacın toplamı.

Düğümleri hangi sırayla ziyaret ettiğinin adı vardır. Sıralı (in-order): önce sol alt ağaç, sonra düğümün kendisi, sonra sağ. Önce kök (pre-order): düğüm, sol, sağ. Sonra kök (post-order): sol, sağ, düğüm. Fark yalnızca düğümle ilgili satırın iki çağrıya göre nerede durduğudur.

Görevler