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

Find Largest Value in Each Tree Row

Problem (yeniden ifade)

İkili ağacın her seviyesindeki en büyük değeri bir dizi olarak döndür.

Sezgi

Standart seviye BFS; her seviye boyutunu tararken max’ı izle.

Yaklaşımlar

Seviye BFS max

Doğrulanmadı

Zaman O(n)Alan O(w)

Fikir. Her seviye için, seviye dizisi üzerinde max.

Yürüyüş. Seviyeler [1], [3,2], [5,3,9] → [1,3,9].

Trade-off. BFS doğal; derinlikle 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 largestValues(root: TreeNode | null): number[] {
  if (!root) return [];
  const res: number[] = [];
  const q: TreeNode[] = [root];
  while (q.length) {
    const size = q.length;
    let m = -Infinity;
    for (let i = 0; i < size; i++) {
      const n = q.shift()!;
      m = Math.max(m, n.val);
      if (n.left) q.push(n.left);
      if (n.right) q.push(n.right);
    }
    res.push(m);
  }
  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 largestValues(root: TreeNode | null): number[] {
  if (!root) return [];
  const res: number[] = [];
  const q: TreeNode[] = [root];
  while (q.length) {
    const size = q.length;
    let m = -Infinity;
    for (let i = 0; i < size; i++) {
      const n = q.shift()!;
      m = Math.max(m, n.val);
      if (n.left) q.push(n.left);
      if (n.right) q.push(n.right);
    }
    res.push(m);
  }
  return res;
}

Şablon bağlantısı

Ağaç BFS seviye bazlı agrega.

Yansıma

Seviye boyu kadar gez, o satırın en büyüğü. Başlangıcı 0 yapmak negatif satırı yanlış yazar; ilk düğümle başla.
Boş ağaç boş liste. Tek düğüm o değer. Eşit maksimum bir kez yazılır.
Satırdaki sıra önemli değil; yalnızca max. Çocuklar yine soldan sağa.