Kalıp #17
Ağaç BFS
ÖnerilenGenişlik, görünümler ve seviye başına toplulaştırma için seviye sırası.
Ne zaman kullanılır
Cevap seviyelere, seviyede soldan sağa sıraya veya derinliğe göre en yakın düğümlere bağlıysa.
Tanıma ipuçları
- Seviye sırası dolaşım
- Sağ yan görünüm / seviye başına max
- Zigzag / seviye ortalamaları
Yaygın tuzaklar
- Döngüden önce seviye boyutunu yakalamamak (kuyruk seviye ortasında büyür)
- Zigzag'ta yalnızca çıktıyı ters çevirmeyi unutup kuyruğu bozmak
- Gerçek seviye sırası gerekirken DFS derinliği kullanmak
90 saniyelik tanıma egzersizi
Hangisi en iyi uyuyor?
- Seviye sırası dolaşım
- Sağ yan görünüm / seviye başına max
- Zigzag / seviye ortalamaları
Interactive
Zihinsel model
Değişmezin tam adım adım anlatımı. Duraklat, noktalara tıkla veya ← → kullan. Her adımı kendi cümlelerinle anlatmayı hedefle.
queue = [3] · level 0
Tree BFS is still a real tree. Queue starts with the root only.
Nasıl düşünülür
Kökü kuyruğa koy. Her seviyede tam size = queue.length düğüm işle; çocukları kuyruğa ekle. O blok bir seviye. Bloğun en sağı (veya solu) yan görünüm.
Etkileşimli model gerçek ağaç düzenini çizerken kuyruk her seviyeyi boyar: DFS sayfalarıyla aynı yapı, farklı dolaşım sırası.
Şablon şekilleri
| Şekil | Temel hamle | Notlar |
|---|---|---|
| Seviye listeleri | i in 0..size-1 | node.val push |
| Yan görünüm | Seviyede son (veya ilk) | Bir kez kaydet |
| Zigzag | Alternatif reverse | Veya deque uçları |
Karmaşıklık temeli
O(n) zaman ve O(w) kuyruk alanı (w = max genişlik).
Şablondan probleme
- Kenar durum: boş ağaç.
- Kökü kuyruğa; while queue: boyutu snapshot; seviye dizisi kur.
- Çocukları sol sonra sağ ekle.
- Seviyeyi sonradan işle (ters, max, ortalama).
Şablon
TypeScript, Python ve C#’te aynı iskelet. Değişmezi uyarla; yapıyı koru.
/** Tree BFS template: level-order values. */
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 levelOrder(root: TreeNode | null): number[][] {
if (!root) return [];
const res: number[][] = [];
const q: TreeNode[] = [root];
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);
}
res.push(level);
}
return res;
}
/** Tree BFS template: level-order values. */
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 levelOrder(root: TreeNode | null): number[][] {
if (!root) return [];
const res: number[][] = [];
const q: TreeNode[] = [root];
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);
}
res.push(level);
}
return res;
}
- 1#102 Binary Tree Level Order TraversalRehbermedium
- 2#103 Binary Tree Zigzag Level Order TraversalRehbermedium
- 3#199 Binary Tree Right Side ViewRehbermedium
- 4#515 Find Largest Value in Each Tree RowRehbermedium
- 5#637 Average of Levels in Binary TreeRehbereasy
- 6#662 Maximum Width of Binary TreeRehbermedium