İkili ağacı serileştirme ve geri okuma

Problem

Bir ikili ağacı tek bir String'e çeviren serialize ve bu string'den birebir aynı yapıdaki ağacı geri kuran deserialize metotlarını yaz. Format tamamen sana kalmış; tek şart, deserialize(serialize(root)) işleminin aynı şekil ve aynı değerlerde bir ağaç üretmesi. Değerler negatif olabilir ve tekrar edebilir.

      1
     / \
    2   3
       / \
      4   5

serialize   -> "1,2,#,#,3,4,#,#,5,#,#"   (bu çözümün formatı)
deserialize -> aynı ağaç

serialize(null) -> "#"
deserialize("#") -> null

Netleştirme soruları

• Değer aralığı ne; negatif ya da çok basamaklı değer var mı? (Ayırıcı gerekir.)
• Değerler benzersiz mi? (Değilse "preorder + inorder" ikilisi yetmez.)
• Çıktı insan tarafından okunabilir mi olmalı, yoksa kompaktlık mı önemli? (Metin mi binary mi?)
• Codec durumsuz (stateless) mı olmalı? (Evet; serileştirme durumunu sınıf alanında tutmamak gerekir.)
• Ağaç ne kadar büyük ve derin olabilir? (Özyineleme ve string boyutu.)

İpuçları

Yaklaşım

Neden "basit liste" yetmez: Sadece preorder (ya da sadece inorder) değerler aynı değer kümesine sahip birden fazla ağaca karşılık gelir. Preorder + inorder ikilisi yapıyı belirler ama sadece değerler benzersizse; ayrıca iki liste ve O(n) bir harita gerektirir.

Null işaretli preorder (seçilen çözüm): Her düğümü "değer, sol alt ağaç, sağ alt ağaç" sırasıyla yaz; boş çocukları # ile yaz. Bu dizi yapıyı eksiksiz tanımlar, çünkü okuyucu her an "şu an hangi yuvayı dolduruyorum" bilgisine sahiptir. Okuma, yazmanın aynası olan bir özyinelemedir ve token'lar bir iterator'dan sırayla tüketilir; global indeks ya da sınıf alanı gerekmez.

BFS (seviye sırası) alternatifi: LeetCode'un kendi gösterimi budur. Kuyrukla yazılır ve okunur; özyineleme olmadığı için derin ağaçta stack riski yoktur. Kod biraz daha uzundur, çünkü okurken ebeveynleri bir kuyrukta tutup token'ları ikişer ikişer çocuklara dağıtmak gerekir.

Format kararları: Ayırıcı (,) çok basamaklı ve negatif değerleri güvenle ayırır. Daha kompakt bir format için değerler DataOutputStream ile 4 byte olarak yazılıp, yapı her düğüm için 2 bitlik "sol var / sağ var" bayraklarıyla kodlanabilir.

Java çözümü

import java.util.Iterator;
import java.util.List;

public final class Codec {

    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; }
    }

    private static final String NULL_MARK = "#";
    private static final String SEPARATOR = ",";

    /** Preorder (kök, sol, sağ); boş çocuklar NULL_MARK ile yazılır. */
    public String serialize(TreeNode root) {
        StringBuilder out = new StringBuilder();
        writePreorder(root, out);
        return out.toString();
    }

    public TreeNode deserialize(String data) {
        Iterator<String> tokens = List.of(data.split(SEPARATOR)).iterator();
        return readPreorder(tokens);
    }

    private void writePreorder(TreeNode node, StringBuilder out) {
        if (!out.isEmpty()) out.append(SEPARATOR);
        if (node == null) {
            out.append(NULL_MARK);
            return;
        }
        out.append(node.val);
        writePreorder(node.left, out);
        writePreorder(node.right, out);
    }

    private TreeNode readPreorder(Iterator<String> tokens) {
        String token = tokens.next();
        if (token.equals(NULL_MARK)) return null;
        int val = Integer.parseInt(token);
        TreeNode left = readPreorder(tokens);     // aynı sırayla oku: önce sol alt ağacın tamamı
        TreeNode right = readPreorder(tokens);
        return new TreeNode(val, left, right);
    }
}

Ayrıntılar: StringBuilder.isEmpty() Java 15 ile geldi; ilk token'dan önce ayırıcı yazmamak için kullanılıyor. String.split ardışık boş token'ları sondan siler ama bu formatta boş token oluşmaz. Codec hiçbir alan tutmadığı için thread-safe'tir ve aynı nesne eşzamanlı kullanılabilir.

Karmaşıklık

• Zaman: Her iki yön O(n). n düğüm için n + 1 tane # yazılır; toplam token sayısı 2n + 1.
• Bellek: O(n) çıktı string'i ve okurken token listesi; ek olarak O(h) özyineleme stack'i.

Kenar durumlar ve testler

Testler main içinde çalıştırıldı:

• Örnek ağacın tam string formatı: "1,2,#,#,3,4,#,#,5,#,#", ve geri okunan ağacın yapısal eşitliği.
• Boş ağaç: "#" ve geri null.
• Negatif değerler, Integer.MIN_VALUE ve Integer.MAX_VALUE.
• Tüm değerleri aynı (1) olan ağaç: yapı korunuyor.
• 1 -> sağ 2 ile 2 -> sol 1 farklı string'ler üretiyor (inorder'ları aynı).
• 1.000 rastgele ağaç (değerler -1000..1000, tekrarlı) gidiş-dönüş testi.

Derinlik uyarısı: Bu çözüm iki yönde de özyinelemelidir. Varsayılan 1 MB stack'le yapılan denemede 8.000 düğümlük zincir ağaçta soğuk JVM'de StackOverflowError alındı; -Xss8m ile 10.000 düğüm geçti. Derinliği kontrol edilemeyen girdi için BFS formatını ya da açık stack'li iteratif preorder'ı tercih et.

Mülakatçı için

Bu soru tasarım kararlarını konuşturur: format seçimi, null gösterimi, ayırıcı, durumsuzluk, boyut. İyi aday önce formatı bir örnekle kağıda yazar, sonra kodlar. "Neden preorder?" sorusuna "okuma sırasında her an hangi yuvayı doldurduğumu bilmemi sağlıyor" gibi mekanizma odaklı bir cevap ararsın.

Gözlemlenecek tipik hatalar: global/statik indeks kullanmak (codec ikinci kez çağrıldığında bozulur), # olmadan değer yazmak, ayırıcısız sayı yazmak (12 bir düğüm mü iki düğüm mü?), deserialize'da yazma sırasından farklı bir sıra izlemek.

İpucu zamanlaması: İlk 5 dakikada format seçemeyen adaya ilk ipucunu ver. Kodlama sırasında indeks yönetiminde takılırsa iterator önerisi (üçüncü ipucu) çoğunlukla yeterlidir.

Takip sorusu 1: Ağaç bir BST ise formatı nasıl küçültürsün? Beklenen: null işaretlerine gerek yok; preorder değerler yeterli, çünkü okurken (low, high) aralığıyla hangi değerin hangi alt ağaca ait olduğu bulunur (LeetCode 449). O(n) okuma.

Takip sorusu 2: Bu ağaç bir servisten diğerine her istekte gidiyor ve ağ maliyeti önemli. Ne yaparsın? Beklenen: binary format (değer için 4 byte, yapı için bit bayrakları), sıkıştırma (gzip), şema evrimi için Protobuf gibi bir format; insan okunabilirliği ile boyut arasındaki takas.

Takip sorusu 3: N-ary ağaç (her düğümün değişken sayıda çocuğu var) için formatı genişlet. Beklenen: her düğümden sonra çocuk sayısını yazmak ya da çocuk listesini bir bitiş işaretiyle kapatmak (LeetCode 428).

Benzer problemler

• Serialize and Deserialize BST (LeetCode 449)
• Serialize and Deserialize N-ary Tree (LeetCode 428)
• Construct Binary Tree from Preorder and Inorder Traversal (LeetCode 105)
• Find Duplicate Subtrees (LeetCode 652)
• Encode and Decode Strings (LeetCode 271)