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

Binary Tree Right Side View

Problem (yeniden ifade)

Sağ taraftan görünen düğümlerin değerlerini döndür (yukarıdan aşağıya).

Sezgi

Seviye seviye BFS; her seviyedeki son düğüm en sağdakidir.

Yaklaşımlar

Level-order son düğüm

Doğrulanmadı

Zaman O(n)Alan O(w)

Fikir. standart seviye kuyruğu; her turda level[^1].val ekle.

Yürüyüş. [1,2,3,null,5,null,4] → [1,3,4].

Trade-off. Derinlik map’li DFS de çalışır; BFS tree-bfs şablonudur.

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

Şablon bağlantısı

Tree BFS seviye cevapları.

Yansıma

Her seviyenin son düğümü sağdan görünen. Yalnızca sağ omurgaya bakmak, sağ çocuğu olmayan solu kaçırır.
Soldan sağa tarayıp sonuncuyu yazmak ile sağdan sola tarayıp ilkini yazmak aynı düğüm mü?
null kök boş. Tek düğüm kendisi.