Bir binary tree'nin maksimum derinliğini (yüksekliğini) bulan fonksiyonu yazın.

Bir düğümün derinliği = 1 + max(sol alt ağacın derinliği, sağ alt ağacın derinliği). Boş ağacın derinliği 0'dır. Bu, ağaç sorularının en temel özyineleme kalıbıdır.

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

def max_depth(root):
    if root is None:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

İteratif (BFS) çözüm

Seviye seviye gezip kaç seviye olduğunu sayarız; çok derin (dengesiz) ağaçlarda stack taşmasını önler.

from collections import deque

def max_depth_bfs(root):
    if not root:
        return 0
    q, depth = deque([root]), 0
    while q:
        depth += 1
        for _ in range(len(q)):
            node = q.popleft()
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
    return depth

Karmaşıklık

• Zaman: O(n), her düğüm bir kez ziyaret edilir.
• Bellek: özyinelemede O(h) (h = yükseklik; dengeli ağaçta O(log n), zincir şeklinde O(n)), BFS'te en geniş seviye kadar O(w).

Aynı kalıbı kullanan sorular

• Minimum derinlik (dikkat: yalnızca yaprağa kadar olan yollar sayılır).
• Balanced Binary Tree: her düğümde sol ve sağ yükseklik farkı en fazla 1 mi?
• Diameter of Binary Tree: her düğümde sol + sağ yüksekliği hesaplayıp maksimumu tutmak.