İkili ağacın sağdan görünümü

Problem

Bir ikili ağacın tam sağ tarafında durduğunu düşün. Her derinlikte sana en yakın, yani o katmanın en sağındaki düğümü görürsün; arkadakiler onun gölgesinde kalır. Yukarıdan aşağıya doğru gördüğün değerleri liste olarak döndür.

      7
     / \
    3   9
     \
      6

Çıktı: [7, 9, 6]

Dikkat: 6, 9'un değil 3'ün çocuğu, yani sol alt ağaçta. Ama üçüncü katmanda başka düğüm olmadığı için sağdan bakan kişi onu görür.

Girdi: [1, 2, null, 3]   (sola uzanan zincir)
Çıktı: [1, 2, 3]

Netleştirme soruları

• Ağaç boşsa boş liste mi dönmeli? (Evet.)
• "Görünür" tanımı katmanın en sağdaki düğümü mü, yoksa sadece sağ çocuklar mı? Bunu örnekle teyit etmek önemli; soru tam olarak bu yanlış anlamayı yakalamak için tasarlanmış.
• Ağacın derinliği ne kadar olabilir? (Özyinelemeli DFS ile iteratif BFS arasındaki seçimi etkiler.)
• Soldan görünüm de istenecek mi? (Takip sorusu olarak sık gelir; çözümü buna kolay uyarlanır yazmak avantajdır.)

İpuçları

Yaklaşım

Sık yapılan yanlış: Kökten başlayıp hep sağ çocuğa inmek. İlk örnekte [7, 9] döner ve sol alt ağaçtaki 6 kaçar. Mülakatçının asıl gözlemlemek istediği, adayın bu tuzağı kendi örneğiyle yakalayıp yakalamadığıdır.

Kaba çözüm: Önce tüm katmanları (LeetCode 102'deki gibi) liste olarak çıkarıp her katmanın son elemanını almak. O(n) zaman, ama tüm değerleri saklamak gereksiz bellek harcar.

BFS ile: Katman şablonunu aynen kullan; iç döngüde i == levelSize - 1 olan düğüm, kuyruğa soldan sağa eklendiği için katmanın en sağındaki düğümdür. Sadece onu sonuca ekle.

DFS ile (sağ önce): dfs(node, depth) sağ çocuğu soldan önce ziyaret eder. Bir derinliğe ilk ulaşan düğüm, o derinliğin en sağdaki düğümüdür; depth == result.size() kontrolü "bu derinlik için henüz kimse eklenmedi" demektir. Kod daha kısadır; bellek O(h) olur. Ancak özyinelemelidir.

Java çözümü

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

public final class RightSideView {

    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<Integer> rightSideView(TreeNode root) {
        List<Integer> view = new ArrayList<>();
        if (root == null) return view;

        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                if (i == levelSize - 1) view.add(node.val);   // katmanın en sağdaki düğümü
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        return view;
    }
}

Soldan görünüm istenirse tek değişiklik koşulu i == 0 yapmaktır. Bu esneklik, BFS versiyonunu mülakatta iyi bir varsayılan yapar.

Karmaşıklık

• Zaman: O(n); her düğüm bir kez kuyruğa girip çıkar.
• Bellek: O(w) kuyruk (w en geniş katman; en kötü O(n)), çıktı O(h). DFS versiyonunda O(h) stack; zincirde O(n), dengeli ağaçta O(log n).

Kenar durumlar ve testler

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

• Sol alt ağacın daha derin olduğu ağaç ([7, 3, 9, null, 6]): [7, 9, 6]. Bu, "sadece sağa in" hatasını yakalayan ana testtir.
• Klasik şekil [1, 2, 3, null, 5, null, 4]: [1, 3, 4].
• Boş ağaç: []; tek düğüm: [42].
• Sola uzanan zincir: her düğüm görünür, [1, 2, 3].
• 500 rastgele ağaçta BFS sonucu, sağ-önce DFS referans çözümüyle karşılaştırıldı; hepsi aynı.

Rastgele karşılaştırma tekniği (iki farklı algoritmayı birbirine karşı çalıştırmak) mülakatta yazılmaz ama kendi pratiğinde hatalı varsayımları bulmanın en hızlı yoludur.

Mülakatçı için

Bu soru, adayın kod yazmadan önce kendi örneğini üretip gereksinimi test etmesini ölçmek için iyidir. Örneği bilerek sadece dengeli bir ağaçla ver; aday "sol alt ağaç daha derin olursa?" diye sorarsa güçlü bir sinyaldir. Sormadan "hep sağa in" yazarsa, ilk örneği (7, 3, 9, -, 6) dry run olarak iste; kendi hatasını bulması, sana söylemenden daha değerli bir gözlemdir.

İpucu zamanlaması: Yanlış yaklaşımla kod yazmaya başlarsa hemen durdurma; 3-4 dakika bırak, sonra dry run iste. Doğru fikre ulaşınca ikinci ipucu çoğu zaman gerekmez. DFS çözümünü yazan adaya derin ağaçta ne olacağını sor.

Takip sorusu 1: Hem soldan hem sağdan görünümü tek geçişte döndür. Beklenen: BFS'te i == 0 ve i == levelSize - 1 koşullarını aynı döngüde kontrol etmek; tek düğümlü katmanda iki görünüm aynı düğümü içerir.

Takip sorusu 2: Ağacın "alttan görünümü" (bottom view): her yatay mesafe (sütun) için en alttaki düğüm. Beklenen: BFS sırasında her düğüme yatay koordinat vermek (sol -1, sağ +1), TreeMap<Integer, Integer> ile sütun başına son görülen değeri tutmak; O(n log n).

Takip sorusu 3: Ağaç bir veritabanındaki kategori hiyerarşisi ve her katman ayrı bir sorgu. Kaç sorgu atarsın? Beklenen: katman başına bir WHERE parent_id IN (...) sorgusu (h sorgu), ya da recursive CTE ile tek sorgu; N+1 probleminden kaçınmak.

Benzer problemler

• Binary Tree Level Order Traversal (LeetCode 102)
• Binary Tree Zigzag Level Order Traversal (LeetCode 103)
• Populating Next Right Pointers in Each Node (LeetCode 116)
• Find Largest Value in Each Tree Row (LeetCode 515)
• Vertical Order Traversal of a Binary Tree (LeetCode 987)