Coding Interview Prep · Ders

Çap, Yükseklik ve Dengeli Ağaçlar

Çap, Yükseklik ve Dengeli Ağaçlar, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 3. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.

İkili Ağacın Yüksekliği

height (veya maksimum derinlik), ikili ağacın kökünden herhangi bir yaprağa giden en uzun yolun uzunluğudur. Özyinelemeli olarak hesaplanır: herhangi bir düğümün height değeri 1 + max(height(left), height(right)) olur; boş düğümler için temel durum 0'dır. Bu son sıralı hesaplama temeldir; height, çapın, denge kontrolünün ve AVL ağacı döndürmelerinin yapı taşıdır.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def height(root):
    if not root:
        return 0
    return 1 + max(height(root.left), height(root.right))

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.left.left.left = TreeNode(6)
print(height(root))  # 4

Çap: En Uzun Yol

İkili ağacın çapı, herhangi iki düğüm arasındaki en uzun yolun uzunluğudur (yol kökten geçebilir veya geçmeyebilir). Yol uzunluğu kenarlarla ölçülür. Herhangi bir düğümden geçen çap height(left) + height(right) değerine eşittir. Genel çap, ağaçtaki tüm düğümler için bu değerlerin en büyüğüdür.

def diameter_of_binary_tree(root):
    max_diameter = [0]  # use list to allow closure mutation

    def dfs(node):
        if not node:
            return 0
        left_h = dfs(node.left)
        right_h = dfs(node.right)
        # Diameter through this node
        max_diameter[0] = max(max_diameter[0], left_h + right_h)
        return 1 + max(left_h, right_h)  # height for parent

    dfs(root)
    return max_diameter[0]

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(diameter_of_binary_tree(root))  # 3

Çap İçin Tek DFS Geçişi

Naif yaklaşım her düğümde height() çağırır ve dengeli bir ağaç için O(n²) zaman alır. En iyi çözüm, height değerini hesaplayıp çapı tek bir DFS geçişinde günceller. Temel fikir, özyinelemeli dfs() işlevinin aynı anda iki amaca hizmet etmesidir: üst düğüm için height değerini döndürürken yan etki olarak genel maksimum çapı günceller. Bu çift amaçlı son sıralı kalıp, birçok ağaç probleminde görülür.

# O(n^2) NAIVE: recomputes height for every node
def diameter_naive(root):
    if not root:
        return 0
    through_root = height(root.left) + height(root.right)
    in_left = diameter_naive(root.left)
    in_right = diameter_naive(root.right)
    return max(through_root, in_left, in_right)

# O(n) OPTIMAL: single DFS pass (shown in previous scene)
# The naive version is O(n^2) because height() is O(n)
# and it is called for every node.
print('Naive: O(n^2) | Optimal single-pass: O(n)')

Dengeli İkili Ağaç Kontrolü

Bir ikili ağaç, her düğümün sol ve sağ alt ağaçlarının height değerleri arasındaki fark en fazla birse height açısından dengelidir. Kaba kuvvet yaklaşımı her düğümde height() çağırır ve O(n²) zaman alır. En iyi yaklaşım aynı tek geçiş hilesini kullanır: ‘dengeli değil’ durumunu belirtmek için -1 döndürür ve bu değeri yukarıya aktarır; böylece herhangi bir düğümün dengeli olmadığı bulunur bulunmaz işlem erken sonlandırılır.

def is_balanced(root):
    def check(node):
        if not node:
            return 0
        left = check(node.left)
        if left == -1:
            return -1  # propagate early exit
        right = check(node.right)
        if right == -1:
            return -1
        if abs(left - right) > 1:
            return -1  # unbalanced here
        return 1 + max(left, right)  # height if balanced

    return check(root) != -1

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.left.left = TreeNode(5)  # too deep on left
print(is_balanced(root))  # False

Özel İşaret Değeri Döndürme Deseni

Özel işaret değeri (dengeli değil durumu için -1 veya özel bir demet) döndürmek, bir DFS yardımcı işlevinin iki tür bilgiyi bildirmesi gerektiğinde kullanılan yaygın bir desendir: hesaplanan sonuç ve bir kısıtın ihlal edilip edilmediği. İstisna oluşturmak veya genel bayraklar kullanmak yerine hatayı dönüş türünde kodlayın. Bu yaklaşım temizdir, genel durumdan kaçınır ve diğer özyinelemeli yardımcılarla doğal biçimde birleştirilebilir.

# General pattern: return (is_valid, computed_value)
def balanced_height(node):
    if not node:
        return True, 0
    left_ok, left_h = balanced_height(node.left)
    if not left_ok:
        return False, 0  # short-circuit
    right_ok, right_h = balanced_height(node.right)
    if not right_ok:
        return False, 0
    balanced = abs(left_h - right_h) <= 1
    return balanced, 1 + max(left_h, right_h)

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
ok, h = balanced_height(root)
print(ok, h)  # True 2

Düğümler ve Kenarlar Açısından Çap

Problem ifadesine dikkat edin: LeetCode #543 çapı kenarlarla ölçerken bazı problemler düğümlerle ölçer. Düğüm sayısına ihtiyacınız varsa bir düğümden geçen çap height(left) + height(right) + 1 olur (düğümün kendisi için 1 eklenir). Kenar sayısına ihtiyacınız varsa +1'i eklemeyin. Kodlamaya başlamadan önce bunu mülakat yapan kişiyle mutlaka netleştirin.

def diameter_in_nodes(root):
    max_path = [0]

    def dfs(node):
        if not node:
            return 0
        left_h = dfs(node.left)
        right_h = dfs(node.right)
        # Path through this node in NODE count
        nodes_through = left_h + right_h + 1
        max_path[0] = max(max_path[0], nodes_through)
        return 1 + max(left_h, right_h)

    dfs(root)
    return max_path[0]

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(diameter_in_nodes(root))  # 4 nodes: 4-2-1-3 or 5-2-1-3

Yol Toplamı: Herhangi Bir Kökten Yaprağa Yol

Yol toplamı problemi şunu sorar: Kökten yaprağa giden yollardan herhangi birinin toplamı hedef değere eşit mi? DFS kullanın ve aşağı doğru ilerlerken hedef değerden geçerli düğümün değerini çıkarın. Bir yaprakta, kalan hedefin yaprağın değerine eşit olup olmadığını kontrol edin. Bu, kalan toplamı parametre olarak aktardığınız ön sıralı bir DFS'dir; yukarıdan aşağıya özyinelemenin klasik bir örneğidir.

def has_path_sum(root, target):
    if not root:
        return False
    # Leaf node: check if we've exactly hit the target
    if not root.left and not root.right:
        return root.val == target
    remaining = target - root.val
    return (has_path_sum(root.left, remaining) or
            has_path_sum(root.right, remaining))

root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(2)
print(has_path_sum(root, 22))  # True: 5+4+11+2=22

Maksimum Yol Toplamı (Zor Varyant)

Maksimum yol toplamı (LeetCode #124) çok daha zordur: yol yalnızca kökten yaprağa gitmek zorunda değildir, herhangi bir düğümde başlayıp bitebilir ve değerler negatif olabilir. Her düğümde dört seçeneği değerlendirin: yalnızca düğüm, düğüm + sol dal, düğüm + sağ dal veya düğüm + her iki dal. Bu seçeneklerden yalnızca ilk üçü üst düğüme doğru uzatılabilir; dördüncü seçenek ise genel maksimum için sonlandırıcı adaydır.

def max_path_sum(root):
    max_sum = [float('-inf')]

    def gain(node):
        if not node:
            return 0
        # Only take positive contributions
        left = max(gain(node.left), 0)
        right = max(gain(node.right), 0)
        # Best path through this node (can't go both ways upward)
        max_sum[0] = max(max_sum[0], node.val + left + right)
        # Return the best single-branch gain for parent
        return node.val + max(left, right)

    gain(root)
    return max_sum[0]

root = TreeNode(-10)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(max_path_sum(root))  # 42: 15+20+7

AVL Ağaçları ve Kendini Dengeleme

AVL ağacı, ekleme ve silme işlemlerinden sonra döndürmeler gerçekleştirerek height dengesi özelliğini koruyan bir BST'dir. Her düğüm, {-1, 0, 1} aralığında kalması gereken bir denge katsayısı (height(sağ) - height(sol)) saklar. Bir ihlal oluştuğunda tekli veya ikili döndürme dengeyi O(1) zamanda yeniden sağlar; böylece toplam height O(log n) düzeyinde kalır ve tüm işlemlerin O(log n) olması garanti edilir.

# Balance factor = height(right) - height(left)
# AVL invariant: balance factor in {-1, 0, 1} for every node

# Four violation types and their fixes:
# LL (left-heavy left child): single right rotation
# RR (right-heavy right child): single left rotation
# LR (right-heavy left child): left rotate child, then right rotate root
# RL (left-heavy right child): right rotate child, then left rotate root

# Knowing this is enough for interviews; you rarely implement
# full AVL in an interview but must discuss the concept.
print('AVL maintains O(log n) height via rotations')

Simetrik Ağaç Kontrolü

Bir ikili ağaç, kendisinin ayna görüntüsüyse simetriktir. Özyinelemeli olarak kontrol edin: eksen üzerindeki her karşılık gelen düğüm çifti aynı değerlere sahip ve alt ağaçları birbirinin aynasıysa ağaç simetriktir. Şunları kontrol eden bir yardımcı is_mirror(left, right) tanımlayın: ikisi de boşsa (uygun), yalnızca biri boşsa (uygun değil), değerler eşitse ve iç/dış alt ağaçlar birbirinin aynasıysa.

def is_symmetric(root):
    def is_mirror(left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        return (left.val == right.val and
                is_mirror(left.left, right.right) and
                is_mirror(left.right, right.left))

    return is_mirror(root.left, root.right)

sym = TreeNode(1)
sym.left = TreeNode(2)
sym.right = TreeNode(2)
sym.left.left = TreeNode(3)
sym.right.right = TreeNode(3)
print(is_symmetric(sym))  # True

nosym = TreeNode(1)
nosym.left = TreeNode(2)
nosym.right = TreeNode(2)
nosym.left.right = TreeNode(3)
print(is_symmetric(nosym))  # False

Yükseklik ve Çap Bilgilerini Birleştirme

Bir yardımcı işlevin aynı anda yüksekliği döndürüp genel sonucu güncellediği tek geçişli son sıralı dolaşım kalıbı, birçok problemde yeniden kullanılabilir: çap, maksimum yol toplamı, dengeyi kontrol etme, iyi düğümleri sayma ve daha fazlası. Her zaman şunu sorun: “Üst düğümün her alt düğümden hangi bilgiye ihtiyacı var?” Bu, dönüş değeridir. “Bu düğüme özgü hangi hesaplama yapılır?” Bu da genel yanıtı günceller. Bu ayrıştırma, zor ağaç problemlerini çözmek için gereken temel beceridir.

# Reusable template for post-order dual-purpose DFS:
def tree_problem(root):
    result = [float('-inf')]  # or 0 depending on problem

    def dfs(node):
        if not node:
            return 0  # base return (height, count, etc.)
        left_val = dfs(node.left)
        right_val = dfs(node.right)
        # --- Update global result using both children ---
        candidate = left_val + right_val  # example: diameter
        result[0] = max(result[0], candidate)
        # --- Return info needed by PARENT ---
        return 1 + max(left_val, right_val)  # example: height

    dfs(root)
    return result[0]

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(tree_problem(root))  # diameter = 2

Hızlı Kontrol

Bu dersteki Veri Yapıları & Algoritmalar — Kodlama Mülakatı Hazırlığı kavramlarını anlayıp anlamadığınızı test edin.

Ders Özeti

Bu derste şunları öğrendiniz: özyinelemeli son sıralı DFS kullanarak yükseklik hesaplama, iki amaçlı bir DFS yardımcısıyla tek bir O(n) geçişte çap hesaplama ve erken çıkış belirteciyle denge kontrolü. Sırada yol toplamı problemleri ve en düşük ortak ata var.

Sıkça Sorulan Sorular

“Çap, Yükseklik ve Dengeli Ağaçlar” dersi ücretsiz mi?

Evet — “Çap, Yükseklik ve Dengeli Ağaçlar” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.

“Çap, Yükseklik ve Dengeli Ağaçlar” dersinde ne öğreneceğim?

Her iki değeri de döndüren bir yardımcı kullanarak tek bir DFS geçişinde ağacın çapını ve yüksekliğini hesaplayın, ardından ağacın yükseklik açısından dengeli olup olmadığını denetleyin. Coding Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.

Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?

Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 3. dersidir.

“Çap, Yükseklik ve Dengeli Ağaçlar” dersi ne kadar sürer?

Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.

Bu Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?

Evet. Her Coding Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.

Bu kursun tüm dersleri

← Coding Interview Prep Sayfasına Dön