Invert Binary Tree

Q: ما هو التعقيد الزمني لعكس شجرة ثنائية؟

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

سهلاجتياز الأشجار

+10

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

اعكس الشجرة: بدّل الابن الأيسر والابن الأيمن لكل عقدة، بحيث تصبح الشجرة كلها صورة مرآة. أعد الشجرة المعكوسة بالتنسيق نفسه، من دون عناصر -1 في النهاية.

الدالة

invertTree(tree: integer-array) → integer-array

treeinteger-array: الشجرة الثنائية بترتيب المستويات، مع استخدام -1 للدلالة على موضع فارغ
تُرجعinteger-array: الشجرة المعكوسة بترتيب المستويات، دون إدخالات ‎-1‎ في النهاية

القيود

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

أمثلة

المدخلات: tree = [5, 3, 8, 1, 4, -1, 9]
المخرجات: [5, 8, 3, 9, -1, 4, 1]
الشرح: يتبادل ابنا الجذر 3 و8 موضعيهما. تحتهما، يعود 1 و4 اللذان كانا أسفل 3 بترتيب 4 و1، أما 8، الذي كان له ابن أيمن فقط هو 9، فأصبح لديه الآن ابن أيسر.

المدخلات: tree = [2, 7, -1, 6]
المخرجات: [2, -1, 7, -1, -1, -1, 6]
الشرح: السلسلة 2، 7، 6 تميل إلى اليسار، وصورتها المعكوسة تميل إلى اليمين. ينتقل 7 من الفهرس 1 إلى الفهرس 2، وينتقل 6 من الفهرس 3 إلى الفهرس 6، لذا تكون الإجابة أطول من المُدخل، مع -1 في كل موضع فارغ قبل العقدة الأخيرة.

المدخلات: tree = [1, -1, -1]
المخرجات: [1]
الشرح: العقدة المفردة هي انعكاسها الخاص. المدخلان -1 هما حشو، وتحذف الإجابة كل -1 في النهاية.

+14 اختبارات مخفية عند الإرسال

سؤال إضافي

كيف تتحقق مما إذا كانت الشجرة صورةً مرآتيّةً لنفسها، باستخدام أزواج الفهارس نفسها ولكن من دون إنشاء نسخة معكوسة؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

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

الاستدعاء الذاتي الذي يضع كل عقدة في فهرسها المعكوس

الفكرة

أولًا، كيفية التنقّل في المصفوفة. للعقدة عند الفهرس i ابن أيسر عند 2*i+1 وابن أيمن عند 2*i+2. لا يكون الابن حقيقيًا إلا إذا كان فهرسه داخل المصفوفة وكانت القيمة هناك لا تساوي -1. في [5, 3, 8, 1, 4, -1, 9]، للجذر 5 العقدتان 3 و8 عند الفهرسين 1 و2، وللعقدة 8 عند الفهرس 2 موضع أيسر فارغ عند 5 والعقدة 9 عند 6.

والآن الانعكاس. يبقى الجذر عند الفهرس 0. يصبح الفرع الأيسر للعقدة هو الفرع الأيمن لنسختها المنعكسة، ويصبح فرعها الأيمن هو الفرع الأيسر. لذا، إذا انتقلت العقدة عند الفهرس src إلى الفهرس dst في الإجابة، ينتقل ابنها الأيسر إلى 2*dst+2 وابنها الأيمن إلى 2*dst+1. اكتب place(src, dst): انسخ القيمة، ثم استدعِ place(2*src+1, 2*dst+2) وplace(2*src+2, 2*dst+1). يعود التنفيذ فورًا إذا كان الموضع فارغًا. في المثال الأول، تنتقل العقدة 3 عند الفهرس 1 إلى 2، لذا ينتقل ابنها الأيسر 1 إلى 6 وابنها الأيمن 4 إلى 5.

لا تغيّر العقدة مستواها أبدًا، لذا يبقى فهرسها المنعكس ضمن المستوى نفسه الذي كان فيه فهرسها الأصلي. قرّب الطول إلى العدد الكامل التالي من المستويات (1, 3, 7, 15, ...)، واملأ هذا العدد من الخانات بالقيمة -1، ثم احذف عناصر -1 من نهاية المصفوفة. في المثال الثاني، يُقرّب الطول 4 إلى 7، ما يوفّر مساحة للقيمة 6 عند الفهرس 6.

يوضع كل عنصر مرة واحدة، وتُملأ المصفوفة الناتجة وتُقلَّم مرة واحدة، لذا يكون الزمن O(n) لمصفوفة طولها n. تستهلك المصفوفة الناتجة ذاكرة O(n)، ويستهلك مكدس الاستدعاءات O(h)، وبحد أقصى 14 إطارًا هنا، وهذا ما يجعل الاستدعاء الذاتي آمنًا في هذه المسألة.

الخوارزمية

قرّب الطول إلى الأعلى ليصبح size = 2^k - 1 واملأ مخرجات بهذا الحجم بالقيمة -1.
اكتب place(src, dst): إذا كان src يتجاوز النهاية أو كانت قيمة tree[src] هي -1، فأعِد التنفيذ.
وإلا فاضبط out[dst] = tree[src]، ثم استدعِ place(2*src+1, 2*dst+2) وplace(2*src+2, 2*dst+1).
استدعِ place(0, 0)، واحذف القيم -1 اللاحقة، ثم أعد المخرجات.

def invertTree(tree):
    n = len(tree)
    size = 1
    while size < n:  # round up to whole levels, so every mirrored index fits
        size = 2 * size + 1
    out = [-1] * size

    def place(src, dst):
        if src >= n or tree[src] == -1:
            return
        out[dst] = tree[src]
        place(2 * src + 1, 2 * dst + 2)  # the left subtree goes to the right
        place(2 * src + 2, 2 * dst + 1)  # the right subtree goes to the left

    place(0, 0)
    last = size - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

البحث بالعرض أولًا باستخدام طابور من أزواج الفهارس

الفكرة

تعمل الأزواج نفسها دون استدعاء ذاتي. ضع (0, 0) في قائمة انتظار: الجذر، والموقع الذي ينتقل إليه. خذ زوجًا (src, dst) من مقدمة قائمة الانتظار، وانسخ tree[src] إلى out[dst]، ثم أضف كل ابن موجود إلى قائمة الانتظار مع وجهته المعكوسة: الابن الأيسر 2*src+1 مع 2*dst+2، والابن الأيمن 2*src+2 مع 2*dst+1.

هذه هي الطريقة التكرارية الكلاسيكية لعكس الشجرة. عند استخدام كائنات العقد، تأخذ عقدة من قائمة الانتظار، وتبدّل ابنيها، ثم تضيفهما إلى القائمة. هنا تُكتب عملية التبديل في فهرس الوجهة بدلًا من ذلك، لأن المصفوفة لا تستطيع تبديل شجرتين فرعيتين كاملتين في خطوة واحدة. تدخل كل عقدة موجودة إلى قائمة الانتظار مرة واحدة، حاملةً الموقع الدقيق الذي تنتمي إليه، لذا ينتهي المطاف بكل عقدة في موضعها المعكوس ضمن المخرجات. في المثال الأول تكون الأزواج الناتجة (0, 0)، (1, 2)، (2, 1)، (3, 6)، (4, 5)، (6, 3).

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

الخوارزمية

قرّب الطول إلى الأعلى ليصبح عددًا صحيحًا من المستويات، واملأ مصفوفة خرج بهذا الحجم بالقيمة -1.
ضع الزوج (0, 0) في طابور.
خذ زوجًا (src, dst) من مقدمة الطابور واضبط out[dst] = tree[src].
أضف إلى الطابور (2*src+1, 2*dst+2) و(2*src+2, 2*dst+1) لكل ابن يقع ضمن حدود المصفوفة ولا تساوي قيمته -1.
عندما يصبح الطابور فارغًا، احذف عناصر -1 الزائدة في النهاية وأعِد الخرج.

def invertTree(tree):
    n = len(tree)
    size = 1
    while size < n:  # round up to whole levels, so every mirrored index fits
        size = 2 * size + 1
    out = [-1] * size
    queue = [(0, 0)]  # pairs: index in tree, index of its mirrored spot in out
    head = 0
    while head < len(queue):
        src, dst = queue[head]
        head += 1
        out[dst] = tree[src]
        left, right = 2 * src + 1, 2 * src + 2
        if left < n and tree[left] != -1:
            queue.append((left, 2 * dst + 2))  # the left child goes to the right
        if right < n and tree[right] != -1:
            queue.append((right, 2 * dst + 1))  # the right child goes to the left
    last = size - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

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

وصف عملية عكس الشجرة نفسها موجز. تأتي الأخطاء من المصفوفة: حجمها ونهايتها وما الذي ينقله تبديل عنصرين فعليًا.

تبديل tree[2*i+1] وtree[2*i+2] في موضعيهما. هذا يبدّل قيمتين، لكنه لا يبدّل الشجرتين الفرعيتين تحتهما. فتبديل الفهرسين 1 و2 في المثال الأول يُبقي 1 و4 معلّقين تحت 8.
جعل طول الناتج مساويًا لطول المدخل. قد ينتهي موضع عقدة بعد عكس الشجرة بعد آخر فهرس في المدخل، كما يحدث مع 6 في المثال الثاني. اجعل حجم الناتج يكفي لمستويات كاملة.
نسيان اقتطاع النهاية. لا تتضمن الإجابة -1 في نهايتها، سواء للمدخلات المكمّلة بالقيم أو للأشجار التي ينتهي عكسها قبل انتهاء المدخل.
عكس المصفوفة بأكملها. هذا يخلط المستويات: ستصبح آخر ورقة هي الجذر.
تجاهل التحقق من الحدود. قد يتجاوز فهرس الابن نهاية المدخل، لأن المصفوفة قد تنتهي مباشرةً بعد آخر عقدة.
الخلط بين الإزاحة في Lua وR، حيث تبدأ المصفوفات من 1. أبقِ الفهارس تبدأ من 0 لحساب 2*i+1 واقرأ tree[i + 1].

أسئلة شائعة4

ماذا يعني عكس شجرة ثنائية؟

يحوّل عكس الشجرة الثنائية إياها إلى صورتها المرآوية: عند كل عقدة، يتبادل الفرعان الفرعيان الأيسر والأيمن موضعيهما. يبقى الجذر في مكانه، وتصبح الورقة الأيسر هي الورقة الأيمن، ويتحول المسار المتجه إلى اليسار إلى مسار متجه إلى اليمين. ويعيد عكس الشجرة مرتين الشجرةَ الأصلية.

ما هو التعقيد الزمني لعكس شجرة ثنائية؟

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

كيف تعكس شجرة ثنائية دون استخدام الاستدعاء التكراري؟

استخدم طابورًا أو مكدسًا. ابدأ بالجذر، وفي كل مرة تُخرج فيها عقدة، بدّل طفليها الأيسر والأيمن وأدخلهما. تُبدَّل كل عقدة مرة واحدة، بأي ترتيب تُخرجها به البنية. في تمثيل المصفوفة، أدرج أزواج الفهارس في الطابور بدلًا من ذلك، واكتب كل عقدة مباشرةً في موضعها المناظر المعكوس.

لماذا يؤدي عكس الشجرة الثنائية إلى عكس ترتيب كل مستوى؟

يعكس التناظر اليسار واليمين في كل مكان، لذا تظهر العقد في كل مستوى بترتيب معاكس. في التخزين بترتيب المستويات، يعني ذلك عكس مقطع المصفوفة الخاص بكل مستوى: فالمقطع [1, 4, -1, 9] من المثال الأول يصبح [9, -1, 4, 1]. ويُعد عكس كل مستوى، بعد ملء المستوى الأخير بقيم -1، حلاً ثالثًا بتعقيد O(n) لا يعمل إلا مع تخطيط هذه المصفوفة.

Python

def invertTree(tree):
    # اكتب الكود هنا

حالات الاختبار

الحالة 1

الحالة 2

الحالة 3

المدخلات

tree = [5, 3, 8, 1, 4, -1, 9]

المتوقع

[5, 8, 3, 9, -1, 4, 1]