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 Zigzag Level Order Traversal

Problem (yeniden ifade)

Seviye sırası değerleri, ama her seviyede left→right ve right→left arasında dönüşümlü.

Sezgi

BFS seviyeleri; tek seviyeleri ters çevir (veya deque yönü kullan).

Yaklaşımlar

Seviye BFS + reverse

Doğrulanmadı

Zaman O(n)Alan O(w)

Fikir. Seviyeyi her zamanki gibi topla; derinlik tekse push’tan önce ters çevir.

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

Trade-off. Deque insert-front isteğe bağlı şeker; reverse net.

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

Şablon bağlantısı

Seviye post-process’li tree BFS.

Yansıma

Seviye BFS aynı. Tek numaralı seviyelerin listesini ters çevirmek zigzag’ı verir.
Kuyruğa her zaman soldan sağa ekle. Ters çevirme yalnızca o seviyenin çıktısında.
Tek düğümde ters çevirme görünmez. Çarpık ağaçta her satırda bir düğüm.