خوارزميةاحترافي
اجتياز الشجرة بالعرض
زُر الشجرة مستوى بعد مستوى، مستخدماً طابوراً لتذكّر العقدة التالية.
- الزمن
- O(n)
- الذاكرة
- O(n)
تتبّعها خطوة بخطوة
الخطوة 1 من 15
1function levelOrder(root) {2 const queue = [root], out = [];3 while (queue.length > 0) {4 const node = queue.shift();5 out.push(node.val);6 if (node.left) queue.push(node.left);7 if (node.right) queue.push(node.right);8 }9 return out;10}- queue
- = [4]
- out
- = []
- 4
- 2
- 6
- 1
- 3
- 5
- 7
نضع الجذر، 4، في الطابور.
درس احترافي
افتح الشرح الكامل
هذا الدرس جزء من الخطة الاحترافية، التي تفتح كل خطوة في كل درس، إضافة إلى تدريبات الأنماط وتقارير الإتقان.
اطّلع على الأسعاركيف تعمل
البحث بالعرض يزور كل عقد المستوى الواحد قبل النزول إلى ما تحته. الطابور يحفظ الترتيب: خذ العقدة من المقدّمة، وأخرجها، وأضف أبناءها في الخلف. ينضمّ الأبناء دائماً خلف كل ما ينتظر، لذا يكتمل المستوى كله قبل أن يبدأ التالي. الفكرة نفسها تجد أقصر مسار في رسم بياني غير موزون. الزمن O(n)، والذاكرة O(n) للطابور.
تدرّب على اكتشاف هذا النمط →