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]]
- الشرح
- للجذر
4ابنان هما9و2عند الفهرسين 1 و2. الفهرس 3 فارغ، لذا يكون المستوى الثالث هو6(الفهرس 4، تحت 9)، ثم8و5(الفهرسان 5 و6، تحت 2). أما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اللاحقة أي شيء.
+15 اختبارات مخفية عند الإرسال
سؤال إضافي
هل يمكنك إرجاع المستويات بترتيب متعرج، الأول من اليسار إلى اليمين، والثاني من اليمين إلى اليسار، وهكذا، دون ترتيب أي مستوى؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
تقع العقدتان الابنتان للفهرس
iعند2*i+1و2*i+2. إذا زرت دائمًا العقد الأقرب إلى الجذر أولًا، وانتقلت من اليسار إلى اليمين بينها، فما ترتيب مقابلة العقد؟يعيد الطابور العُقد بالترتيب الذي أضفتها به. إذا أضفت أبناء العُقدة عند إخراجها، فستُخرَج العُقد مستوىً واحدًا في كل مرة. وما تبقّى هو تحديد موضع انتهاء أحد المستويات وبدء المستوى التالي.
في بداية كل جولة، يحتوي الطابور على مستوى واحد بالضبط. اقرأ حجمه
s، وأخرج منهsعقد إلى قائمة جديدة، وأضف أبناءها، بدءًا بالابن الأيسر، مع تخطي-1والفهارس التي تتجاوز النهاية. توقّف عندما يصبح الطابور فارغًا.
الحل
يجب إخراج كل مستوى في قائمة مستقلة، مرتبة من اليسار إلى اليمين. تزور عملية البحث بعرض الشجرة، باستخدام طابور، العُقد بهذا الترتيب تمامًا. والفكرة الإضافية الوحيدة هي معرفة موضع نهاية المستوى: في بداية كل دورة، يحتوي الطابور على المستوى الحالي كله ولا شيء سواه، لذا يخبرك حجمه بعدد العُقد التي ينبغي أخذها. كما تنجح عملية المرور بعمق، ما دامت تتعقب عمق كل عقدة وتزور اليسار قبل اليمين.
البحث أولًا بالعمق، مُرتَّب حسب العمق
الفكرة
أولًا، التنقّل في المصفوفة. يقع الابن الأيسر للفهرس i عند 2i+1، والابن الأيمن عند 2i+2. يكون الابن مفقودًا عندما يتجاوز فهرسه نهاية المصفوفة أو عندما يحتوي على -1. في المثال 1، يقع ابنا 9 (الفهرس 1) عند الفهرسين 3 و4، وتحتوي خانتاهما على -1 و6، لذا ليس لـ 9 سوى ابن أيمن.
والآن، اجتز الشجرة بترتيب العمق أولًا ومرّر إلى كل عقدة عمقها، بحيث يكون عمق الجذر 0. احتفظ بقائمة واحدة لكل عمق. عندما تصل إلى عقدة عمقها d، ألحِق قيمتها بالقائمة d؛ وإذا كان لديك حتى الآن d قوائم فقط، فهذه أول عقدة في مستوى جديد، لذا أنشئ قائمة جديدة أولًا.
لماذا يظهر كل مستوى من اليسار إلى اليمين؟ لأن الاجتياز ينهي الشجرة الفرعية اليسرى للعقدة بالكامل قبل الانتقال إلى الشجرة الفرعية اليمنى. خذ عقدتين في المستوى نفسه: عند النقطة التي يتفرع فيها مساراهما من الجذر، يتجه أحدهما يسارًا والآخر يمينًا، ويصل الاجتياز إلى العقدة اليسرى أولًا. في المثال 1، يكون الترتيب 4, 9, 6, 3, 2, 8, 5، ما يملأ القوائم على النحو التالي: [4]، [9, 2]، [6, 8, 5]، [3].
تُزار كل عقدة مرة واحدة، لذا يكون الزمن O(n) لعدد n من العقد، وتحتوي القوائم على n قيمة. ولا يتجاوز عمق الاستدعاء عمق الشجرة، وهو 15 مستوى على الأكثر هنا. يستخدم إصدار R مكدسًا صريحًا بدلًا من ذلك، إذ يدفع الابن الأيمن قبل الابن الأيسر لكي يُسحب الأيسر أولًا، ثم يجمع القيم بحسب العمق باستخدام split.
الخوارزمية
- أنشئ قائمة فارغة للمستويات.
- زُر الجذر بعمق 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، لذا تغادر جميع عقد المستوى d قبل أن تغادر أي عقدة من المستوى d+1، وداخل المستوى الواحد تغادر العقد من اليسار إلى اليمين.
ينتج عن ذلك تسلسل واحد من القيم بترتيب المستويات. لتقسيمه إلى مستويات، اقرأ حجم الطابور في بداية الجولة. في تلك اللحظة، يحتوي الطابور على المستوى الحالي بالضبط: فقد غادره المستوى السابق ولم تصل إليه أي عقدة من المستوى التالي. أخرج هذا العدد من العقد وضعه في قائمة واحدة. أما الأبناء الذين تضيفهم، فينتمون إلى الجولة التالية.
في المثال 1، يبدأ الطابور بالشكل [4]: أخرج عقدة واحدة، فيكون الصف [4]، وتدخل 9, 2. أخرج عقدتين، فيكون الصف [9, 2]، وتدخل 6, 8, 5. أخرج 3 عقد، فيكون الصف [6, 8, 5]، وتدخل 3. أخرج عقدة واحدة، فيكون الصف [3]، ويصبح الطابور فارغًا.
تدخل كل عقدة الطابور وتغادره مرة واحدة، لذا فالزمن هو O(n). يحتوي الطابور على عدد لا يتجاوز تقريبًا عدد عقد مستوى واحد، أي ما يصل إلى 16384 عقدة في أعمق مستوى من شجرة كاملة عمقها 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على أنه قيمة. الخانة الفارغة ليست عقدة، لذا لا تُضاف أبدًا إلى صف أو إلى الطابور. - نسيان التحقق من الحدود. قد تقع أبناء أعمق العقد بعد نهاية المصفوفة، لذا تحقّق من
child < nقبل قراءةtree[child]. - إرجاع مستويات فارغة. لا تحتوي عناصر
-1اللاحقة على أي عقد، لذا تكون الإجابة عن[7, -1, -1]هي[[7]]، وليست[[7], []].
أسئلة شائعة4
ما التعقيد الزمني لاجتياز الشجرة الثنائية بترتيب المستويات؟
يزور كلٌّ من الحل بالبحث في العرض أولًا والحل بالبحث في العمق أولًا كل عقدة مرة واحدة، لذا يعملان في زمن O(n) لعدد n من العقد. تحتوي الإجابة نفسها على n قيمة، لذا تكون المساحة O(n). وإضافةً إلى ذلك، يحتوي الطابور على عدد لا يتجاوز تقريبًا عدد العقد في أوسع مستوى، ولا يتجاوز عمق الاستدعاء التكراري ارتفاع الشجرة.
كيف تعرف أين ينتهي أحد المستويات في البحث بالعرض أولًا؟
اقرأ حجم قائمة الانتظار في بداية كل جولة. في تلك اللحظة، تحتوي قائمة الانتظار على عقد مستوى واحد بالضبط، لذا فإن إخراج هذا العدد من العقد يزيل المستوى ولا شيء أكثر. وتنجح طريقتان أخريان أيضًا: الاحتفاظ بالمستوى الحالي والمستوى التالي في قائمتين منفصلتين، أو إضافة علامة بعد كل مستوى.
هل يمكن إجراء اجتياز المستوى باستخدام البحث بالعمق أولاً؟
نعم. مرّر إلى كل عقدة عمقها وأضف قيمتها إلى القائمة الخاصة بذلك العمق. ما دام الاجتياز يزور الشجرة الفرعية اليسرى قبل الشجرة الفرعية اليمنى، فستكون كل قائمة مرتبة من اليسار إلى اليمين. وتعقيده أيضًا O(n)؛ أما الاجتياز بالعرض فهو الأنسب مباشرةً لأنه ينتج المستويات بالترتيب.
المصفوفة مخزّنة بالفعل مستوىً تلو الآخر. لماذا لا نقرأها على شكل شرائح؟
بالنسبة إلى هذا التنسيق، يعمل ما يلي: المستوى d يشغل الفهارس من 2^d-1 إلى 2^(d+1)-2، لذا يمكنك جمع القيم غير الفارغة من كل نطاق والتوقف عند أول نطاق لا يحتوي على أي قيم. لكن في المقابلة، تأتي الشجرة عادةً على شكل كائنات عقد ذات مؤشري left وright، من دون فهارس لتحديد نطاق منها. ويُعدّ الاجتياز المعتمد على الطابور هو ما ينطبق على هذا الشكل وعلى تنويعات مثل الترتيب المتعرج أو العرض من الجانب الأيمن.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def levelOrder(tree):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
tree = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]
المتوقع
[[4], [9, 2], [6, 8, 5], [3]]