İkili ağacı katman katman dolaşma

Problem

Bir ikili ağacın kökü veriliyor. Düğüm değerlerini derinliğe göre gruplayarak döndür: önce kökün bulunduğu katman, sonra onun çocukları, sonra torunları... Her katmanın içinde değerler soldan sağa sıralı olmalı. Sonuç, her elemanı bir katmanın değer listesi olan bir liste.

        8
      /   \
     4     12
    /     /  \
   2     10   14

Girdi (seviye sırası): [8, 4, 12, 2, null, 10, 14]
Çıktı: [[8], [4, 12], [2, 10, 14]]

Girdi: []      (boş ağaç)
Çıktı: []

Bu soru tek başına kolaydır; asıl değeri, "katman sınırını nasıl bilirim?" sorusunu doğru çözen BFS şablonunu öğretmesidir. Sağdan görünüm, zigzag dolaşım, katman ortalaması, minimum derinlik gibi onlarca soru aynı şablonun küçük varyasyonudur.

Netleştirme soruları

• Ağaç boş olabilir mi? Boşsa boş liste mi dönmeli, null mı? (Boş liste.)
• Düğüm sayısının üst sınırı ne? Ağaç çok derin (zincir gibi) olabilir mi? Bu, özyinelemeli çözümün stack'i taşırıp taşırmayacağını belirler.
• Katman içinde sıra soldan sağa mı? Yoksa zigzag gibi bir varyasyon mu bekleniyor?
• Sonucu List<List<Integer>> olarak mı döneceğim, yoksa katmanları bir callback/stream ile tüketmek mi istiyoruz? (Çok büyük ağaçta tüm sonucu bellekte tutmamak için.)

İpuçları

Yaklaşım

Naif fikir: Önce ağacın yüksekliğini (h) bul, sonra her derinlik d için kökten başlayıp "d derinliğindeki düğümleri topla" diye ayrı bir DFS çalıştır. Her DFS O(n) olduğundan toplam O(n·h); zincir gibi bir ağaçta O(n²) olur.

Optimal fikir: BFS ve katman boyutu. BFS düğümleri kökten uzaklık sırasıyla ziyaret eder, yani katman sırası BFS'in doğal sırasıdır. Tek sorun katman sınırıdır. Gözlem şu: bir katmanı işlemeye başladığın anda kuyrukta sadece o katmanın düğümleri vardır (önceki katmanın tamamı çıktı, sonraki katmandan henüz kimse eklenmedi). Dolayısıyla o anki queue.size() tam olarak katmanın genişliğidir. Bu sayıyı döngüden önce bir değişkene sabitlemek kritiktir; döngü koşuluna i < queue.size() yazarsan çocuklar eklendikçe sınır kayar ve katmanlar birbirine karışır.

Alternatif: DFS ve derinlik parametresi. dfs(node, depth) ile gezip levels.get(depth).add(val) yapmak da doğru sonuç verir (önce sol, sonra sağ çocuğa inildiği için katman içi sıra korunur). Kısa ve şıktır ama özyinelemeli olduğu için zincir ağaçta derinlik kadar stack çerçevesi harcar.

Java çözümü

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

public final class LevelOrderTraversal {

    static final class TreeNode {
        final int val;
        TreeNode left, right;
        TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        if (root == null) return levels;

        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int levelSize = queue.size();                 // bu katmanda kaç düğüm var: döngüden ÖNCE sabitle
            List<Integer> level = new ArrayList<>(levelSize);
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) queue.offer(node.left);   // ArrayDeque null kabul etmez
                if (node.right != null) queue.offer(node.right);
            }
            levels.add(level);
        }
        return levels;
    }
}

ArrayDeque hem kuyruk hem stack için doğru seçimdir; LinkedList'ten daha az nesne üretir. Ancak null kabul etmez, bu yüzden çocukları eklemeden önce null kontrolü şarttır (zaten gereksiz düğüm eklemek istemeyiz). Katman listesini levelSize kapasitesiyle açmak küçük bir ayrıntıdır ama mülakatçıya boyutun önceden bilindiğini fark ettiğini gösterir.

Karmaşıklık

• Zaman: O(n). Her düğüm kuyruğa bir kez girer, bir kez çıkar.
• Bellek: Çıktı hariç O(w); w ağacın en geniş katmanıdır. Tam (complete) bir ikili ağaçta son katman yaklaşık n/2 düğüm içerir, yani en kötü durum O(n). Zincir ağaçta kuyruk hiç 1'i geçmez. DFS alternatifinin ek belleği ise O(h) stack'tir; dengeli ağaçta O(log n), zincirde O(n).

Kenar durumlar ve testler

Çözüm, main içindeki şu testlerle derlenip çalıştırıldı:

• Yukarıdaki örnek ağaç: [[8], [4, 12], [2, 10, 14]].
• null kök: boş liste (null değil).
• Tek düğüm, negatif değer: [[-5]].
• Sola eğik zincir (1 -> 2 -> 3 -> 4): dört tek elemanlı katman.
• Boşluklu ağaç ([1, 2, 3, null, 4, 5]): eksik çocuklar katman sırasını bozmuyor, [[1], [2, 3], [4, 5]].
• 200.000 düğümlük sağa eğik zincir: iteratif BFS stack taşırmadan 200.000 katman döndürdü. Aynı ağaçta özyinelemeli DFS varsayılan 1 MB thread stack'iyle StackOverflowError verir.

Mülakatta dry run için en iyi girdi, katmanların farklı genişlikte olduğu bir ağaçtır; eşit genişlikli bir örnek, queue.size()'ı döngü koşuluna yazma hatasını gizleyebilir.

Mülakatçı için

Bu soru genelde bir ısınma sorusudur ya da daha büyük bir sorunun (sağdan görünüm, zigzag, serileştirme) ilk adımıdır. 10-15 dakikada bitmesi beklenir. Gözlemlenecek asıl şey adayın katman sınırını nasıl yönettiğidir: levelSize'ı döngüden önce sabitleyen aday şablonu biliyordur; null işaretçi (sentinel) ya da (node, depth) çifti kullanan aday da doğrudur, sadece biraz daha fazla kod yazar.

İpucu zamanlaması: Aday iki dakika içinde BFS'i önermezse ilk ipucunu ver. BFS'i yazıp katmanları ayıramıyorsa ikinci ipucu ("işlemeye başlarken kuyrukta kimler var?") genelde yeterlidir. Üçüncü ipucuna ihtiyaç duyan aday için bu bir eksi sinyal değil, ama soru zor kategoride değildir; sonraki soruda zorlamayı artır.

Takip sorusu 1: Katmanları zigzag sırayla (bir soldan sağa, bir sağdan sola) döndür. Beklenen: aynı BFS, katman listesini ArrayDeque olarak tutup tek katmanlarda addFirst kullanmak ya da listeyi ters çevirmek; kuyruğa ekleme sırası değişmez.

Takip sorusu 2: Ağaç 10 milyon düğümlü ve sonuç belleğe sığmıyor. Beklenen: sonucu toplamak yerine her katmanı bir Consumer<List<Integer>>'a vermek ya da stream etmek; BFS'in tepe belleğinin en geniş katman olduğunu, DFS'in ise yüksekliğe bağlı olduğunu söyleyip hangisinin seçileceğini ağacın şekline bağlamak.

Takip sorusu 3: Her katmanın ortalamasını döndür. Beklenen: toplamı long (ya da double) tutmak; int toplam taşabilir.

Benzer problemler

• Binary Tree Right Side View (LeetCode 199)
• Binary Tree Zigzag Level Order Traversal (LeetCode 103)
• Average of Levels in Binary Tree (LeetCode 637)
• Minimum Depth of Binary Tree (LeetCode 111)
• Serialize and Deserialize Binary Tree (LeetCode 297)