İkili ağaçta en yakın ortak ata

Problem

Bir ikili ağaç (arama ağacı değil) ve ağaçta bulunan iki düğüm p ve q veriliyor. İkisinin de atası olan düğümler arasından en derindekini bul. Bir düğüm kendi atası sayılır; yani p, q'nun atasıysa cevap p'dir.

            10
          /    \
         4      15
        / \    /  \
       2   7  12   20
          / \
         6   9

p = 2, q = 9   -> 4   (2 solda, 9 sağ alt ağaçta; yolları 4'te ayrılıyor)
p = 7, q = 6   -> 7   (7, 6'nın atası; düğüm kendisinin de atası)
p = 6, q = 20  -> 10

Düğümler referansla verilir; değerler benzersiz olsa da karşılaştırma kimlikle yapılmalıdır.

Netleştirme soruları

• p ve q'nun ağaçta olduğu garanti mi? (LeetCode'da evet. Garanti yoksa çözüm değişir; takip sorularına bak.)
• p == q olabilir mi? (Olursa cevap düğümün kendisi.)
• Düğümlerde ebeveyn işaretçisi var mı? (Varsa problem "iki bağlı listenin kesişimi"ne dönüşür.)
• Ağaç bir BST mi? (BST ise değer karşılaştırmasıyla O(h) ve O(1) ek bellekle çözülür; LeetCode 235.)
• Ağaç ne kadar derin olabilir? (Özyineleme riski.)

İpuçları

Yaklaşım

İki yol yaklaşımı: DFS ile kökten p'ye ve q'ya giden yolları liste olarak çıkar, sonra iki listeyi baştan karşılaştırıp son ortak düğümü bul. O(n) zaman, O(h) ek bellek; doğru ama iki geçiş ve geri izleme (backtracking) gerektirir.

Ebeveyn haritası: BFS ile her düğümün ebeveynini bir Map'e yaz, p'nin tüm atalarını bir Set'e koy, sonra q'dan yukarı çıkıp sette ilk bulunan düğümü döndür. İteratiftir (stack riski yok), O(n) zaman ve O(n) bellek. Derin ağaçlarda mülakatçıya söylenmesi gereken alternatif budur.

Tek geçiş özyineleme (optimal): Fonksiyon alt ağaçtan bir "rapor" döndürür:

1. Düğüm null ise null (burada kimse yok).
2. Düğüm p ya da q ise kendisini döndür. Diğer hedef bu düğümün altındaysa cevap zaten bu düğüm; değilse yukarıdaki bir düğüm iki raporu birleştirecek.
3. Sol ve sağ alt ağaçtan raporları al. İkisi de doluysa hedefler bu düğümde ayrılıyor; cevap bu düğüm. Biri doluysa onu yukarı taşı.

Neden doğru? Bir düğüm ancak hedefler farklı alt ağaçlarda olduğunda (ya da kendisi hedeflerden biriyse) LCA olabilir ve böyle bir düğüm ağaçta tektir. Derindeki bir düğüm LCA'yı bulduğunda onu yukarı taşır; üstteki atalar sadece tek taraftan rapor aldığı için cevabı değiştirmez.

Java çözümü

public final class LowestCommonAncestor {

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

    /** p ve q'nun ağaçta bulunduğu varsayılır (problem garantisi). */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;   // kimlik karşılaştırması: ==

        TreeNode fromLeft = lowestCommonAncestor(root.left, p, q);
        TreeNode fromRight = lowestCommonAncestor(root.right, p, q);

        if (fromLeft != null && fromRight != null) return root;    // biri solda, biri sağda: ayrıldıkları nokta
        return fromLeft != null ? fromLeft : fromRight;            // ikisi de aynı tarafta (ya da hiçbiri yok)
    }
}

== bilinçli bir seçimdir. Değer eşitliğiyle (root.val == p.val) karşılaştırmak, tekrar eden değerli ağaçlarda yanlış sonuç verir. Java'ya özgü bir tuzak daha: TreeNode'u record olarak yazarsan equals/hashCode yapısal olur. Ebeveyn haritası yaklaşımında record anahtarlı HashMap kullanmak, her hashCode çağrısında tüm alt ağacı dolaşır (O(n²)) ve aynı şekilli farklı alt ağaçları aynı anahtar sayar. Kimlik tabanlı yapı gerekiyorsa IdentityHashMap kullanılır.

Karmaşıklık

• Zaman: O(n); her düğüm en fazla bir kez ziyaret edilir.
• Bellek: O(h) özyineleme stack'i. Dengeli ağaçta O(log n), zincirde O(n).

Kenar durumlar ve testler

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

• Yukarıdaki ağaçta: (2, 9) için 4, (6, 20) için 10, (7, 6) için 7 (düğüm kendisinin atası), (10, 9) için 10 (kök hedeflerden biri), (12, 12) için 12 (p == q).
• İki düğümlü ağaç: kök.
• Aynı değere sahip üç düğüm (5, 5, 5): sonuç kimlikle doğru, kök.
• 300 rastgele ağaçta sonuç, "p'nin ata kümesini çıkar, q'dan yukarı tırman" kaba çözümüyle karşılaştırıldı; hepsi aynı.

Derinlik uyarısı: Varsayılan 1 MB thread stack'iyle yapılan denemede, 10.000 düğümlü sola eğik zincirde bu özyinelemeli çözüm soğuk JVM'de StackOverflowError verdi; -Xss8m ile geçti. Production kodunda derinliği kontrol edemediğin bir ağaç için ebeveyn haritası ya da açık stack'li iteratif DFS seç.

Mülakatçı için

Bu soru, adayın özyinelemeli bir fonksiyonun ne döndürdüğünü net tanımlayıp tanımlayamadığını ölçer. Güçlü aday kod yazmadan önce "bu fonksiyon alt ağaçta p ya da q varsa onu, ikisi de varsa LCA'yı döndürür" cümlesini kurar. Zayıf aday önce boolean containsP, containsQ gibi yardımcılar yazıp her düğümde tekrar arar (O(n²)); bunu fark edip etmediğini sor.

İpucu zamanlaması: Aday 5 dakikada bir yaklaşıma ulaşamazsa ilk ipucunu (iki yol) ver; iki yol çözümünü yazmak tamamen kabul edilebilir bir sonuçtur. Tek geçiş için ikinci ipucunu ancak iki yol çözümü bittikten sonra ver. Ağacın BST olmadığını özellikle vurgula; BST varsayan aday değer karşılaştırması yapar.

Takip sorusu 1: p ya da q ağaçta olmayabilir; bu durumda null dön. Beklenen: mevcut çözüm, sadece p varsa p'yi döndürür ve yanlış olur. Bulunan hedef sayısını sayan bir sayaç ya da erken dönüşü kaldırıp tüm ağacı gezmek gerekir (LeetCode 1644).

Takip sorusu 2: Düğümlerde parent işaretçisi var, kök verilmiyor. Beklenen: iki işaretçiyle yukarı çıkmak; biri köke ulaşınca diğerinin başlangıç düğümünden devam etmek (iki bağlı listenin kesişimi), O(h) zaman ve O(1) bellek (LeetCode 1650).

Takip sorusu 3: Aynı ağaç üzerinde milyonlarca LCA sorgusu gelecek. Beklenen: ön işleme ile her sorguyu O(log n)'e indiren binary lifting (her düğüm için 2^k'ıncı ata tablosu) ya da Euler turu + RMQ; en azından "ön işleme ile sorgu maliyetini düşürürüm" fikri.

Benzer problemler

• Lowest Common Ancestor of a Binary Search Tree (LeetCode 235)
• Lowest Common Ancestor of a Binary Tree II (LeetCode 1644)
• Lowest Common Ancestor of a Binary Tree III (LeetCode 1650)
• Lowest Common Ancestor of Deepest Leaves (LeetCode 1123)
• Path Sum II (LeetCode 113)