Left View of Binary Tree

Q: ما التعقيد الزمني وتعقيد المساحة للمنظر الأيسر؟

يفحص كلا الحلين كل عقدة مرة واحدة، لذا فالزمن هو O(n) . يحتوي طابور البحث بالعرض على مستوى كامل، أي نحو نصف عقد الشجرة الكاملة. ويحتفظ الاجتياز الذي يبدأ من اليسار باستدعاء واحد لكل مستوى، أي O(h) لعدد h من المستويات.

سهلاجتياز الأشجار الطابور

+10

لديك شجرة ثنائية ممثلة بالمصفوفة root بترتيب الكومة: الجذر عند الفهرس 0، وأبناء الفهرس i عند 2*i+1 (الأيسر) و2*i+2 (الأيمن)، وتشير -1 إلى موضع فارغ. قد تنتهي المصفوفة بعناصر -1 إضافية.

قف إلى يسار الشجرة. في كل مستوى ترى عقدة واحدة، وهي العقدة الأقرب إلى اليسار؛ أما بقية عقد المستوى فتحجبها. أعد القيم التي تراها، من المستوى الأعلى إلى الأسفل.

الدالة

leftView(root: integer-array) → integer-array

rootinteger-array: الشجرة بترتيب الكومة، مع ‎-1‎ للمكان الفارغ
تُرجعinteger-array: القيمة الأبعد إلى اليسار في كل مستوى، بدءًا من المستوى الأعلى

القيود

1 ≤ root.length ≤ 32767
كل root[i] يساوي -1 أو قيمة تحقق 0 ≤ root[i] ≤ 10⁴.
قيم العُقد متميزة.
root[0] لا تكون أبدًا -1، لذا تحتوي الشجرة على عقدة واحدة على الأقل.
قد تنتهي المصفوفة بعناصر -1 إضافية بعد العقدة الأخيرة.
كلا ابني الموضع الفارغ فارغان أيضًا، ولا يزيد ارتفاع الشجرة على 14 مستوى.

أمثلة

المدخلات: root = [3, 8, 5, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, 1]
المخرجات: [3, 8, 6, 1]
الشرح: 8 ورقة، لذا لا يحتوي المستويان الثالث والرابع إلا على 6 (الفهرس 6) و1 (الفهرس 13)، وكلاهما تحت الابن الأيمن 5. مع ذلك، تراهما: [3, 8, 6, 1].

المدخلات: root = [10, -1, -1]
المخرجات: [10]
الشرح: الفهرسان 1 و2 يحتويان على -1، لذا ليس لـ 10 أي أبناء، ويقتصر العرض على الجذر وحده.

المدخلات: root = [1, 2, 3, 4, 5, 6, 7]
المخرجات: [1, 2, 4]
الشرح: شجرة كاملة من ثلاثة مستويات. المواضع الموجودة في أقصى اليسار من المستويات هي الفهارس 0 و1 و3، وتحتوي على 1 و2 و4.

سؤال إضافي

يملأ المستوى d الفهارس من 2^d-1 إلى 2^(d+1)-2. هل يمكنك بناء العرض عبر المرور على تلك النطاقات، من دون استخدام طابور أو استدعاء递归؟ ما تكلفة ذلك على مصفوفة مبطّنة؟

الحل

إن تتبّع الأبناء اليسرى بدءًا من الجذر يفشل عندما تكون الشجرة الفرعية اليسرى أقصر: ففي المثال الأول، تظهر المستويات الأدنى عبر الشجرة الفرعية اليمنى. تريد الوصول إلى العقدة الأولى في كل مستوى. يمنحك البحث بالعرض كل مستوى من اليسار إلى اليمين؛ أما الاجتياز بالعمق الذي يبدأ باليسار، فيصادف أولًا العقدة الواقعة أقصى اليسار في كل مستوى.

بحثٌ بعرض المستوى، أول عقدة في كل مستوى

الفكرة

يعطيك الطابور الذي تتم معالجته على شكل جولات المستويات واحدًا تلو الآخر. في بداية الجولة، يحتوي الطابور على مستوى واحد بالضبط، من اليسار إلى اليمين، لأن كل ابن يُضاف أثناء الجولة يأتي بعده. أخرج هذا العدد من الفهارس، وأضف أبناء كل منها إلى الطابور، بدءًا بالابن الأيسر، واحتفظ بالقيمة الأولى.

في المثال الأول، تكون الجولات [3] و[8, 5] و[6] و[1]، وتحتفظ بالقيم 3 و8 و6 و1. لا يضيف 8 شيئًا، لأن موضعي ابنيه 3 و4 يحتويان على -1.

يدخل كل عُقدة الطابور ويخرج منه مرة واحدة: زمن O(n). يحتوي الطابور على مستوى كامل، يصل إلى 8192 فهرسًا في شجرة كاملة من 14 مستوى.

الخوارزمية

ابدأ طابورًا يحتوي على الفهرس 0، وإجابة فارغة.
ما دام الطابور غير فارغ، اجعل s حجمه وأزل s فهارس. أضف قيمة الفهرس الأول.
لكل فهرس محذوف i، أضف 2i+1 إلى الطابور، ثم 2i+2، مع تخطي الفهارس التي تتجاوز النهاية والعناصر التي تساوي -1.

from collections import deque


def leftView(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 == 0:
                view.append(root[i])  # the first 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

البحث بالعمق أولًا، مع زيارة الابن الأيسر أولًا

الفكرة

تجوّل بترتيب العمق أولًا، في الفرع الأيسر قبل الفرع الأيمن، ومرّر عمق كل عقدة. أول عقدة يصل إليها التجوّل عند العمق d هي العقدة الأيسر في المستوى d. خذ العقدة الأيسر x في مستوى وأي عقدة y تقع إلى يمينها: عند آخر عقدة يشترك المساران فيها، يتجه x يسارًا وy يمينًا، وينهي التجوّل الفرع الأيسر قبل أن يتجه يمينًا.

ينزل التجوّل مستوى واحدًا في كل مرة، لذا عندما يصل لأول مرة إلى العمق d تكون الإجابة محتوية على d قيمة بالضبط. سجّل العقدة عندما يساوي d طول الإجابة؛ فلا حاجة إلى مجموعة للأعماق التي تمت زيارتها.

تُزار كل عقدة مرة واحدة، بزمن O(n)، وتحتفظ الذاكرة باستدعاء واحد لكل مستوى، وبحد أقصى 14 هنا. يحتفظ إصدار R بمكدسه الخاص، ويدفع الابن الأيمن قبل الأيسر.

الخوارزمية

أنشئ إجابة فارغة واستدعِ visit(0, 0).
في visit(i, d)، ارجع فورًا إذا كان i خارج حدود المصفوفة أو كانت قيمة root[i] هي -1.
إذا كان d مساويًا لطول الإجابة، فهذا يعني أن الاجتياز وصل إلى المستوى d للمرة الأولى: أضف root[i].
استدعِ visit(2i+1, d+1)، ثم visit(2i+2, d+1).
أعِد الإجابة بعد انتهاء الاستدعاء الأول.

def leftView(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])
        # Left before right, so the leftmost node of every level comes first.
        visit(2 * i + 1, depth + 1)
        visit(2 * i + 2, depth + 1)

    visit(0, 0)
    return view

أخطاء شائعة وحالات حدّية

اتباع الأبناء اليسرى فقط انطلاقًا من الجذر. في المثال الأول، يتوقف ذلك عند 8 ويفوّت 6 و1.
قراءة الخانة الأولى في كل مستوى، root[2^d-1]. في المثال الأول، تحتوي الخانة الأولى في المستوى الثالث، ذات الفهرس 3، على -1، بينما تقع عقدته الوحيدة عند الفهرس 6.
زيارة الابن الأيمن أولًا في اجتياز العمق أولًا. عندئذٍ تكون أول عقدة تتم زيارتها في كل مستوى هي العقدة الأيمن.
قراءة ابن من دون التحقق من الحدود. للعقدة 1 عند الفهرس 13 موضعا ابنين هما 27 و28، وهما خارج نطاق المصفوفة ذات العناصر الـ14.

أسئلة شائعة3

هل العرض الأيسر هو نفسه الحد الأيسر للشجرة؟

لا. الحد الأيسر هو مسار: يبدأ من الابن الأيسر للجذر، ويتجه يسارًا عندما يكون ذلك ممكنًا، وإلا فيتجه يمينًا، ويتوقف قبل الوصول إلى ورقة. يأخذ المنظر الأيسر عقدة واحدة من أي فرع عند كل مستوى. في المثال الأول، يكون الحد فارغًا، لأن 8 ورقة، لكن المنظر يعرض 8 و6 و1.

ما التعقيد الزمني وتعقيد المساحة للمنظر الأيسر؟

يفحص كلا الحلين كل عقدة مرة واحدة، لذا فالزمن هو O(n). يحتوي طابور البحث بالعرض على مستوى كامل، أي نحو نصف عقد الشجرة الكاملة. ويحتفظ الاجتياز الذي يبدأ من اليسار باستدعاء واحد لكل مستوى، أي O(h) لعدد h من المستويات.

كيف تغيّر الحل للحصول على العرض الصحيح؟

في نسخة البحث بالعرض أولًا، احتفظ بآخر قيمة في كل جولة بدلًا من الأولى. وفي نسخة البحث بالعمق أولًا، زُر الابن الأيمن قبل الأيسر؛ عندها تكون أول عقدة يصل إليها الاجتياز في كل مستوى هي العقدة الواقعة في أقصى اليمين.

def leftView(root):
    # اكتب الكود هنا

اختبار #1

اختبار #2

اختبار #3

وسيط

root = [3, 8, 5, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, 1]

الإخراج المتوقع

[3, 8, 6, 1]