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

Easytree-bfs

Average of Levels in Binary Tree

Problem (yeniden ifade)

Her seviyedeki düğümlerin ortalama değerini double dizisi olarak döndür.

Sezgi

Seviye BFS; her seviye için sum/count.

Yaklaşımlar

Seviye BFS ortalama

Doğrulanmadı

Zaman O(n)Alan O(w)

Fikir. Her seviye boyutu için toplamı biriktir, sum/size ekle.

Yürüyüş. [3,9,20,null,null,15,7] → [3, 14.5, 11].

Trade-off. Seviye sırası ile aynı iskelet; yalnızca toplulaştırma farklı.

Çö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 averageOfLevels(root: TreeNode | null): number[] {
  if (!root) return [];
  const res: number[] = [];
  const q: TreeNode[] = [root];
  while (q.length) {
    const size = q.length;
    let sum = 0;
    for (let i = 0; i < size; i++) {
      const n = q.shift()!;
      sum += n.val;
      if (n.left) q.push(n.left);
      if (n.right) q.push(n.right);
    }
    res.push(sum / size);
  }
  return res;
}

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 averageOfLevels(root: TreeNode | null): number[] {
  if (!root) return [];
  const res: number[] = [];
  const q: TreeNode[] = [root];
  while (q.length) {
    const size = q.length;
    let sum = 0;
    for (let i = 0; i < size; i++) {
      const n = q.shift()!;
      sum += n.val;
      if (n.left) q.push(n.left);
      if (n.right) q.push(n.right);
    }
    res.push(sum / size);
  }
  return res;
}

Şablon bağlantısı

Tree BFS seviye başına toplulaştırma.

Yansıma

Seviye toplamı bölü seviye boyu. Tam sayı bölme ortalamayı keser.
Negatif değerler toplamı düşürür. Tek düğüm kendisi. Boş ağaç boş.
Büyük toplam int’i taşırabilir. Toplamı geniş tut.