Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumtree-bfs

Maximum Width of Binary Tree

Problem (yeniden ifade)

Bir seviyenin genişliği, en soldaki ve en sağdaki null olmayan düğümler arasındaki uzunluktur; aradaki null’lar ağaç tam bir heap’miş gibi sayılır. Tüm seviyeler arasındaki maksimum genişliği döndür.

Sezgi

Her seviyeyi BFS ile dolaşırken heap indeksleri ata: sol çocuk 2i, sağ 2i+1. Genişlik = last − first + 1. Taşmayı önlemek için indeksleri seviye başına normalize et.

Yaklaşımlar

İndeksli BFS

Doğrulanmadı

Zaman O(n)Alan O(w)

Fikir. (node, index) kuyruğu. Her seviye için ilk indeksi kaydet, en iyiyi idx − first + 1 ile güncelle.

Yürüyüş. Kök indeksi 0; 0 ve 3 indekslerinin olduğu seviye → genişlik 4.

Trade-off. İndeks BFS standarttır; derinlik map’li DFS de çalışır.

Çözüm

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 widthOfBinaryTree(root: TreeNode | null): number {
  if (!root) return 0;
  let best = 0;
  const q: { node: TreeNode; idx: number }[] = [{ node: root, idx: 0 }];
  while (q.length) {
    const size = q.length;
    const base = q[0]!.idx;
    let first = 0, last = 0;
    for (let i = 0; i < size; i++) {
      const { node, idx } = q.shift()!;
      const norm = idx - base;
      if (i === 0) first = norm;
      last = norm;
      if (node.left) q.push({ node: node.left, idx: norm * 2 });
      if (node.right) q.push({ node: node.right, idx: norm * 2 + 1 });
    }
    best = Math.max(best, last - first + 1);
  }
  return best;
}

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 widthOfBinaryTree(root: TreeNode | null): number {
  if (!root) return 0;
  let best = 0;
  const q: { node: TreeNode; idx: number }[] = [{ node: root, idx: 0 }];
  while (q.length) {
    const size = q.length;
    const base = q[0]!.idx;
    let first = 0, last = 0;
    for (let i = 0; i < size; i++) {
      const { node, idx } = q.shift()!;
      const norm = idx - base;
      if (i === 0) first = norm;
      last = norm;
      if (node.left) q.push({ node: node.left, idx: norm * 2 });
      if (node.right) q.push({ node: node.right, idx: norm * 2 + 1 });
    }
    best = Math.max(best, last - first + 1);
  }
  return best;
}

Şablon bağlantısı

Konum indeksleriyle tree BFS.

Yansıma

Sol çocuk 2*i, sağ 2*i+1. Genişlik en sağ indeks eksi en sol artı 1.
İndeks derinlikte taşar. Seviye başında en solu 0’a kaydırmak taşmayı keser, farkı korur.
Tek düğüm 1. Eksik sol çocuk sağ indeksi büyütür. Tam seviye 2^(h-1) genişliğindedir.