Ağaç DFS

Nasıl düşünülür

Ebeveynin ihtiyacı olanı döndüren f(node) yaz (yükseklik, is-BST, min/max, düğümden geçen en iyi yol). Önce sol ve sağı çöz, sonra birleştir. Bazen global en iyiyi de güncelle.

Etkileşimli model gerçek ağaç çizimi kullanır (kenarlar + düğümler); değerler ve rozetler yapı boyunca yukarı akar.

Şablon şekilleri

Şekil	Temel hamle	Notlar
Yükseklik döndür	1+max(L,R)	Derinlik, denge
Çok alan döndür	bayrak struct	BST / çap
Sınır geç	low < val < high	BST doğrula

Karmaşıklık temeli

O(n) zaman her düğümü bir kez; alan özyineleme yığını O(h).

Şablondan probleme

1. f(node) dönüş tipini bir cümlede belirt.
2. null için temel durum.
3. Sol/sağ özyinele; birleştir; isteğe bağlı global güncelle.
4. Ebeveynin istediği değeri döndür.

/** Tree DFS template: max depth. */
export class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val; this.left = left; this.right = right;
  }
}
export function maxDepth(root: TreeNode | null): number {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

/** Tree DFS template: max depth. */
export class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val; this.left = left; this.right = right;
  }
}
export function maxDepth(root: TreeNode | null): number {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}