Binary Tree Right Side View
تحتوي المصفوفة root على شجرة ثنائية. يقع الجذر عند الفهرس 0، وتقع عُقد الأبناء للعقدة عند الفهرس i عند 2*i+1 (اليسرى) و2*i+2 (اليمنى)، وتشير -1 إلى موضع فارغ، وقد توجد قيَم إضافية -1 في النهاية.
انظر إلى الشجرة من جانبها الأيمن. يُظهر لك كل مستوى عقدة واحدة بالضبط، وهي العقدة الأبعد إلى اليمين، ويحجب ما تبقى. اذكر تلك القيم بدءًا من مستوى الجذر نزولًا إلى أعمق مستوى.
الدالة
- rootinteger-array
- الشجرة بترتيب الكومة، مع -1 للدلالة على خانة فارغة
- تُرجعinteger-array
- القيمة الموجودة في أقصى اليمين لكل مستوى، بدءًا بالمستوى الأعلى
القيود
1 ≤ root.length ≤ 32767- كل
root[i]إما-1أو قيمة تحقق0 ≤ root[i] ≤ 104. - قيم العقد متميزة.
root[0]لا تساوي أبدًا-1، لذا تحتوي الشجرة على عقدة واحدة على الأقل.- قد تنتهي المصفوفة بإدخالات
-1إضافية بعد العقدة الأخيرة. - كلا ابني الموضع الفارغ فارغان أيضًا، ولا يتجاوز ارتفاع الشجرة
14مستوى.
أمثلة
- المدخلات
- root = [5, 2, 9, 7, 4, -1, 1, -1, 3]
- المخرجات
- [5, 9, 1, 3]
- الشرح
- من اليمين ترى
5و9و1(الفهرس 6). يحتوي المستوى الرابع على3فقط، عند الفهرس 8 تحت7في الشجرة الفرعية اليسرى. لا يصل أي شيء على اليمين إلى هذا العمق، لذا يكون3مرئيًا.
- المدخلات
- root = [6, 0, -1, 8, -1, -1, -1]
- المخرجات
- [6, 0, 8]
- الشرح
- الشجرة عبارة عن سلسلة من الأبناء اليساريين:
6،0،8. يحتوي كل مستوى على عقدة واحدة، لذا ترى العقد الثلاث، مع أن أياً منها ليس ابناً يمينياً.
- المدخلات
- root = [42]
- المخرجات
- [42]
- الشرح
- مصفوفة بطول 1: الجذر
42ليس له أي مواضع للأبناء، وهذا المنظور هو تلك القيمة الواحدة.
سؤال إضافي
كيف يمكنك الحصول على المنظر الجانبي الأيمن لشجرة يمكن أن يكون لكل عقدة فيها أي عدد من الأبناء، مخزّنين في قائمة من اليسار إلى اليمين؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
إن تتبّع الأبناء الأيمنين في المثال 1 يعطينا
5, 9, 1ثم يتوقف. لكن الإجابة تحتوي على قيمة رابعة. من أين أتت؟جمّع العُقد حسب العمق بدلًا من الجانب. اكتب كل مستوى من اليسار إلى اليمين: أين تقع في تلك القائمة العُقدة التي سيرى شخصٌ على اليمين؟
احتفِظ بقائمة
view. نفّذ اجتيازًا عمقيًا مع تتبّع العمق، مع زيارة الابن الأيمن قبل الأيسر، وألحِق عقدةً عندما يساوي عمقها طولview. ويمكن أيضًا استخدام طابور يعالج مستوىً واحدًا في كل جولة: ألحِق العقدة الأخيرة في كل جولة.
الحل
ترى العقدة الواقعة أقصى اليمين في كل مستوى، ولا يشترط أن تكون ابنًا أيمن: فالقيمة الأخيرة في المثال 1 تقع في الفرع الأيسر. يجعل البحث بعرض الشجرة هذه العقدة الأخيرة في كل جولة؛ أما السير بعمق مع البدء باليمين فيصادفها قبل أي عقدة أخرى في مستواها.
البحث بعرض الشجرة، العقدة الأخيرة في كل مستوى
الفكرة
عالج الشجرة مستوىً واحدًا في كل جولة. عند بدء الجولة، يحتوي الطابور على مستوى واحد بالضبط، من اليسار إلى اليمين، لذا يكون آخر فهرس تسحبه من الطابور في الجولة هو العقدة الموجودة في أقصى اليمين من ذلك المستوى، وتُضاف قيمتها إلى الإجابة.
في المثال 1، الجولات هي [5] و[2, 9] و[7, 4, 1] و[3]، وآخر العناصر فيها تعطي 5, 9, 1, 3. المستوى هو ما يحدد النتيجة، لا الجانب: تقع 3 في الفرع الأيسر، لكنها وحيدة في مستواها.
يُضاف كل فهرس إلى الطابور ويُسحب منه مرة واحدة، لذا يكون الزمن O(n). ويتسع الطابور حتى عرض المستوى الأوسع، أي O(n) في أسوأ الحالات.
الخوارزمية
- أضف فهرس الجذر
0إلى قائمة الانتظار. - ابدأ جولة بحفظ طول قائمة الانتظار
s. - أزل
sفهارس من قائمة الانتظار. لكل فهرسi، أضف2i+1إلى قائمة الانتظار، ثم2i+2إذا كانا أقل من طول المصفوفة ولا يساويان-1. - أضف قيمة آخر فهرس أُزيل من قائمة الانتظار في الجولة.
- كرّر حتى تصبح قائمة الانتظار فارغة، ثم أعد الإجابة.
from collections import deque
def rightSideView(root):
n = len(root)
view = []
queue = deque([0]) # node indexes; the root is never empty
while queue:
size = len(queue) # exactly the nodes of the current level
for j in range(size):
i = queue.popleft()
if j == size - 1:
view.append(root[i]) # the last node of this level
for child in (2 * i + 1, 2 * i + 2):
if child < n and root[child] != -1:
queue.append(child)
return viewالبحث بالعمق أولًا، مع البدء بالابن الأيمن
الفكرة
تجوّل بترتيب العمق أولًا، مع تجربة الابن الأيمن قبل الأيسر، واحمل العمق، الذي يساوي 0 عند الجذر. في المرة الأولى التي يصل فيها التجوّل إلى العمق d، تحتوي الإجابة على d قيم بالضبط. ألحِق قيمة العقدة حينها وتجاهل كل عقدة لاحقة في ذلك المستوى.
تلك العقدة الأولى هي العقدة الأيمن: أينما افترق مساران إلى مستوى ما، يتبع التجوّل الفرع الأيمن حتى نهايته قبل أن يعود إلى الفرع الأيسر. في المثال 1، يزور التجوّل 5, 9, 1, 2, 4, 7, 3: ويتجاوز 2 و4 و7، إذ توجد قيمة مسبقًا لأعماقها، ثم يُلحِق 3.
تُزار كل عقدة مرة واحدة، بزمن O(n)، مع استدعاء واحد لكل مستوى على المكدس، وبحد أقصى 14.
الخوارزمية
- ابدأ بإجابة فارغة، واجعل الجذر عند العمق 0.
- تجاوز أي فهرس يتجاوز نهاية المصفوفة أو تكون قيمته
-1. - عندما يساوي طول الإجابة العمق، أضف القيمة: تكون عملية المرور قد وصلت إلى مستوى جديد، ووصلت إليه من اليمين.
- استدعِ تكراريًا الابن الأيمن
2i+2أولًا، ثم الابن الأيسر2i+1، مع التعمق مستوى واحدًا في كل مرة. - أعِد الإجابة.
def rightSideView(root):
n = len(root)
view = []
def visit(i, depth):
if i >= n or root[i] == -1:
return
if depth == len(view): # the first node met on this level
view.append(root[i])
# Right before left, so the rightmost node of every level comes first.
visit(2 * i + 2, depth + 1)
visit(2 * i + 1, depth + 1)
visit(0, 0)
return view
أخطاء شائعة وحالات حدّية
- اتّباع الأبناء الأيمنين فقط انطلاقًا من الجذر. يعطي المثال 1 عندها
[5, 9, 1]ويُفوّت3؛ ويعطي المثال 2[6]. - قراءة الخانة الأخيرة في كل مستوى،
root[2^(d+1)-2]. في المثال 2، تحتوي الخانة ذات الفهرس 6 على-1؛ والعقدة الظاهرة هي8عند الفهرس 3. - تجاهل التحقّق من طول المصفوفة في موضع الابن. في المثال 1،
3هو العنصر الأخير، لذا فإن موضعي ابنيه 17 و18 غير موجودين. - إدراج الابن الأيمن أولًا في الطابور مع الاحتفاظ بآخر عقدة في كل جولة. ينتج عن ذلك المنظور الأيسر،
[5, 2, 7, 3]. - السماح للعقد اللاحقة بالكتابة فوق العقد السابقة أثناء المرور من اليمين أولًا، ما ينتج أيضًا المنظور الأيسر.
أسئلة شائعة3
ما هو التعقيد الزمني وتعقيد المساحة لمشكلة عرض الجانب الأيمن للشجرة الثنائية؟
الزمن هو O(n) لـ n من العُقد، ولا يمكن لأي حل تخطّي العُقد، إذ قد توجد العقدة الواقعة في أقصى اليمين من المستوى في أي موضع. المساحة هي O(w) للطابور، حيث w هو عرض المستوى الأكبر، أو O(h) للمرور بدءًا من اليمين في شجرة ذات h مستويات.
هل يمكن لبحث العمق أولًا من اليسار حلّها؟
نعم، إذا استبدلت القيمة الأولى بدلًا من الاحتفاظ بها. يزور المسح الذي يبدأ من اليسار عُقد كل مستوى من اليسار إلى اليمين، لذا خزّن قيمة كل عقدة عند عمقها، ودع العُقد اللاحقة تستبدل القيم السابقة. ينتهي كل عمق بقيمة عقدته الأبعد إلى اليمين. يظل التعقيد O(n)، لكنه يكتب مرة واحدة لكل عقدة.
هل ينبغي أن أستخدم البحث بالعرض أولًا أم البحث بالعمق أولًا هنا؟
كلاهما خطّي. يتبع البحث بالعرض التعريف، مستوى واحدًا في كل جولة. أما البحث بالعمق فيحتفظ بالمسار الحالي فقط، ما يوفر الذاكرة في شجرة عريضة، كما أن صيغته التكرارية أقصر ببضعة أسطر.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def rightSideView(root):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
وسيط
root = [5, 2, 9, 7, 4, -1, 1, -1, 3]
الإخراج المتوقع
[5, 9, 1, 3]