Binary Tree Level Order Traversal
تحتوي المصفوفة tree على شجرة ثنائية. يقع الجذر عند الفهرس 0، ويقع ابنا العقدة عند الفهرس i عند 2*i+1 (الأيسر) و2*i+2 (الأيمن)، وتشير -1 إلى موضع فارغ، وقد تتبعها عناصر إضافية من -1 في النهاية.
أعِد قيم العقد مستوىً بمستوى: قائمة واحدة لكل مستوى، من الجذر نزولًا إلى أعمق مستوى، مع ترتيب قيم كل مستوى من اليسار إلى اليمين.
الدالة
- treeinteger-array
- الشجرة بترتيب الكومة، مع -1 للدلالة على موضع فارغ
- تُرجعinteger-2d-array
- قائمة واحدة من القيم لكل مستوى، بدءًا بالمستوى الأعلى، وكلٌّ منها من اليسار إلى اليمين
القيود
1 ≤ tree.length ≤ 32767- كل
tree[i]إما-1أو قيمة تحقق0 ≤ tree[i] ≤ 1000. tree[0]لا تساوي أبدًا-1، لذا تحتوي الشجرة على عقدة واحدة على الأقل.- قد تنتهي المصفوفة بعناصر
-1إضافية بعد العقدة الأخيرة. - كلا الفرعين التابعين لموضع فارغ فارغان أيضًا، والعمق لا يزيد عن
14.
أمثلة
- المدخلات
- tree = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]
- المخرجات
- [[4], [9, 2], [6, 8, 5], [3]]
- الشرح
- الفهرس 3 فارغ، لذا فإن
9له ابن أيمن فقط، وهو6. يتكوّن المستوى الثالث من6و8و5، أما3عند الفهرس 9، الواقع أسفل6، فهو وحده في المستوى الرابع.
- المدخلات
- tree = [7, -1, -1]
- المخرجات
- [[7]]
- الشرح
- كلا ابني الجذر هما
-1، لذا تتكوّن الشجرة من العقدة الوحيدة7ولها مستوى واحد.
- المدخلات
- tree = [1, 3, -1, 5, -1, -1, -1]
- المخرجات
- [[1], [3], [5]]
- الشرح
- لكل عقدة ابن أيسر فقط:
3عند الفهرس 1 و5عند الفهرس 3. يحتوي كل مستوى على قيمة واحدة، ولا تضيف القيم-1في النهاية أي شيء.
سؤال إضافي
هل يمكنك إرجاع المستويات بترتيب متعرج، الأول من اليسار إلى اليمين، والثاني من اليمين إلى اليسار، وهكذا، من دون ترتيب أي مستوى؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
تقع العقدتان الابنتان للفهرس
iعند2*i+1و2*i+2. إذا زرت دائمًا العقد الأقرب إلى الجذر أولًا، وانتقلت من اليسار إلى اليمين بينها، فما ترتيب العقد التي ستلتقي بها؟يعيد الطابور العُقد بالترتيب الذي أضفتها به. إذا أضفت أبناء العُقدة عند إخراجها، فستخرج العُقد مستوىً واحدًا في كل مرة. وما يتبقى هو تحديد موضع انتهاء أحد المستويات وبدء المستوى التالي.
في بداية كل جولة، يحتوي الطابور على مستوى واحد بالضبط. اقرأ حجمه
s، وأخرجsمن العقد وضعها في قائمة جديدة، ثم أضف أبناءها، بدءًا بالأيسر، مع تخطي-1والفهارس التي تتجاوز النهاية. توقّف عندما يصبح الطابور فارغًا.
الحل
يجب أن يظهر كل مستوى في قائمة مستقلة من اليسار إلى اليمين. تزور عملية البحث بالعرض أولًا، باستخدام طابور، العقد بهذا الترتيب، وفي بداية كل جولة يحتوي الطابور على مستوى واحد بالضبط، لذا يحدد حجمه عدد العقد التي يجب أخذها. وتنجح أيضًا عملية اجتياز بالعمق أولًا تتتبّع عمق كل عقدة.
البحث بالعمق أولًا، مُرتَّب حسب العمق
الفكرة
اجتز الشجرة بترتيب العمق أولاً، مع تمرير عمق كل عقدة إليها، بحيث يكون عمق الجذر 0، واحتفظ بقائمة لكل عمق. تضيف العقدة عند العمق d قيمتها إلى القائمة d، وتنشئ تلك القائمة إذا كانت أول عقدة تُزار في مستواها.
تكون عناصر كل قائمة مرتبة من اليسار إلى اليمين، لأن الاجتياز يُكمل زيارة الشجرة الفرعية اليسرى للعقدة قبل الانتقال إلى اليمنى. ومن بين عقدتين في المستوى نفسه، تُزار أولاً العقدة التي ينعطف مسارها إلى اليسار عند نقطة تفرّع المسارين. في المثال 1، يملأ ترتيب الزيارة 4, 9, 6, 3, 2, 8, 5 القوائم [4]، [9, 2]، [6, 8, 5]، [3].
تُزار كل عقدة مرة واحدة: الزمن O(n)، مع استدعاء递ي بعمق يصل إلى عمق الشجرة، وبحد أقصى 14 مستوى.
الخوارزمية
- أنشئ قائمة فارغة من المستويات.
- زُر الجذر بعمق 0.
- عند العقدة
iذات العمقd، توقّف إذا كانiيتجاوز النهاية أو كانتtree[i]تساوي-1. - إذا كان هناك
dقوائم فقط، فأضف قائمة فارغة. ألحِقtree[i]بالقائمةd. - زُر
2i+1، ثم2i+2، وكلاهما بعمقd+1.
def levelOrder(tree):
n = len(tree)
levels = []
def visit(i, depth):
if i >= n or tree[i] == -1:
return
if depth == len(levels): # the first node seen on this level
levels.append([])
levels[depth].append(tree[i])
# Left before right, so every level fills from left to right.
visit(2 * i + 1, depth + 1)
visit(2 * i + 2, depth + 1)
visit(0, 0)
return levelsالبحث بالعرض أولًا، مستوى واحد في كل جولة
الفكرة
أخرج عقدة من الطابور وأضف أبناءها، بدءًا بالابن الأيسر. لا يدخل المستوى d+1 إلا بعد مغادرة المستوى d، لذا تغادر العقد مستوىً تلو الآخر، من اليسار إلى اليمين.
لتقسيم هذا التسلسل إلى مستويات، اقرأ حجم الطابور في بداية الجولة. يكون المستوى السابق قد غادر، ولم يصل أيٌّ من المستوى التالي بعد، لذا يحتوي الطابور على المستوى الحالي بالضبط. أخرج هذا العدد من العقد في صف واحد؛ وينتظر أبناؤها الجولة التالية. في المثال 1، تأخذ الجولات 1 و2 و3 و1 عقدة.
تدخل كل عقدة الطابور وتغادره مرة واحدة: زمن O(n). يحتوي الطابور على نحو مستوى واحد، وبحد أقصى 8,192 عقدة في أعمق مستوى من شجرة كاملة ذات 14 مستوى.
الخوارزمية
- ضع فهرس الجذر
0في قائمة الانتظار. - ما دامت قائمة الانتظار غير فارغة، اقرأ حجمها
sوابدأ صفًا فارغًا. - أخرج
sفهارس. لكل فهرسi، أضفtree[i]إلى الصف. - أضف
2i+1، ثم2i+2، إلى قائمة الانتظار عندما يكون الفهرس ضمن حدود المصفوفة ولا يحتوي على-1. - أضف الصف إلى الإجابة وابدأ الجولة التالية.
from collections import deque
def levelOrder(tree):
n = len(tree)
levels = []
queue = deque([0]) # node indexes; the root is never empty
while queue:
row = []
for _ in range(len(queue)): # exactly the nodes of the current level
i = queue.popleft()
row.append(tree[i])
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
queue.append(child)
levels.append(row)
return levels
أخطاء شائعة وحالات حدّية
- قراءة حجم الطابور أثناء إفراغه. في
while (j < queue.length)يزداد الطول مع وصول الأبناء، لذا يتسرّب المستوى التالي إلى الصف الحالي. - إضافة الابن الأيمن قبل الأيسر، أو زيارة الشجرة الفرعية اليمنى أولًا. عندها يصبح المستوى الثاني في المثال 1 هو
[2, 9]. - تجاوز فحص الحدود
child < n. تقع أبناء أعمق العقد بعد نهاية المصفوفة. - الحذف من مقدمة قائمة مصفوفة عادية، ما يؤدي في لغات كثيرة إلى إزاحة الطابور بأكمله في كل مرة. استخدم طابورًا حقيقيًا أو فهرسًا للرأس.
- التعامل مع
-1على أنه عقدة. فهو لا يدخل أبدًا في صف أو في الطابور:[7, -1, -1]تعطي[[7]]، وليس[[7], []].
أسئلة شائعة3
ما هو التعقيد الزمني لاجتياز الشجرة الثنائية بترتيب المستويات؟
يزور كلا الحلين كل عقدة مرة واحدة: يستغرق ذلك زمنًا قدره O(n) لعدد n من العقد. تحتوي الإجابة على n قيمة، لذا تكون المساحة O(n). وإلى جانب ذلك، يحتوي الطابور على عدد من العناصر يقارب عدد العقد في أوسع مستوى، بينما يشغل الاستدعاء التكراري مساحة تتناسب مع ارتفاع الشجرة.
كيف تعرف أين ينتهي أحد المستويات في البحث بعرض الشجرة؟
اقرأ حجم قائمة الانتظار في بداية كل جولة، وخذ هذا العدد بالضبط من العقد. وهناك طريقتان أخريان تعملان أيضًا: الاحتفاظ بالمستوى الحالي والمستوى التالي في قائمتين منفصلتين، أو إضافة علامة إلى قائمة الانتظار بعد كل مستوى.
المصفوفة مخزّنة بالفعل على مستوى كل طبقة. لماذا لا نقرأها على شكل شرائح؟
بالنسبة إلى هذا التنسيق، تعمل الطريقة كالتالي: المستوى d، مع وجود الجذر عند 0، يملأ الفهارس من 2^d-1 إلى 2^(d+1)-2، لذا اجمع القيم غير الفارغة من كل نطاق إلى أن يصبح أحد النطاقات خاليًا. عادةً ما تستخدم المقابلات كائنات عُقد ذات مؤشرات بدلًا من ذلك، والشيء الوحيد الذي ينتقل إلى ذلك الشكل هو قائمة الانتظار.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def levelOrder(tree):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
وسيط
tree = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]
الإخراج المتوقع
[[4], [9, 2], [6, 8, 5], [3]]