Symmetric Tree

Q: ما التعقيد الزمني للشجرة المتماثلة؟

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

Q: كيف تتحقق من أن الشجرة الثنائية متناظرة دون استخدام الاستدعاء التعاودي؟

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

Q: ما الفرق بين شجرة متناظرة وشجرتين متطابقتين؟

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

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

نعم. تحتوي العقدة الواحدة على موضعين فارغين للابنين، وهذان الموضعان الفارغان متناظران. لا تكون العقدة الجذرية التي لها ابن واحد بالضبط متناظرةً أبدًا، لأن هذا الابن يقابل موضعًا فارغًا.

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

+10

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

الدالة

isSymmetric(tree: integer-array) → boolean

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

القيود

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

أمثلة

المدخلات: tree = [1, 2, 2, 3, 4, 4, 3]
المخرجات: true
الشرح: اطوِ الشجرة من المنتصف. يلتقي الرقمان 2 عند الفهرسين 1 و2، ويلتقي الرقمان الخارجيان 3 عند الفهرسين 3 و6، ويلتقي الرقمان الداخليان 4 عند الفهرسين 4 و5.

المدخلات: tree = [1, 2, 2, -1, 3, -1, 3]
المخرجات: false
الشرح: كلتا العقدتين 3 تتدليان على يمين أبويهما. في صورة مرآة، يجب أن يواجه الابن الأيمن للعقدة 2 اليسرى (الفهرس 4) الابن الأيسر للعقدة 2 اليمنى (الفهرس 5)، والفهرس 5 فارغ.

المدخلات: tree = [4, 6, 6, 5, -1, -1, 9]
المخرجات: false
الشرح: الشكل صورة معكوسة: الفهرس 3 يقابل الفهرس 6، وكلاهما يحتوي على عقدة. تختلف قيمتاهما، 5 مقابل 9، لذا فالشجرة غير متناظرة.

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

سؤال إضافي

إذا كان الشكل يعكس نفسه لكن بعض القيم لا تتطابق، فما أقل عدد من قيم العُقد التي يجب تغييرها لجعل الشجرة متناظرة؟

تلميحات

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

فُتح 0 من 3

الحل

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

قارن كل مستوى بنسخته المعكوسة

الفكرة

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

والآن انظر إلى الشجرة مستوىً واحدًا في كل مرة. تكون صورة المرآة متماثلة عند قراءتها من اليسار إلى اليمين ومن اليمين إلى اليسار، لذا يجب أن يُقرأ كل مستوى، مع تضمين مواضعه الفارغة، بالطريقة نفسها في كلا الاتجاهين. في المثال الأول، تُقرأ المستويات أسفل الجذر هكذا: 2 2 و3 4 4 3. وفي المثال الثاني تُقرأ هكذا: 2 2 ثم -1 3 -1 3، وعند عكسها تصبح 3 -1 3 -1، لذا تكون الإجابة false.

يجب أن تبقى المواضع الفارغة ضمن الصف. من دونها، سيُقرأ المستوى السفلي في المثال الثاني هكذا: 3 3، وسيجتاز الاختبار. اكتب مدخلًا لكل موضع ابن لكل عقدة حقيقية في المستوى، واكتب -1 للموضع الفارغ؛ كما أن أبناء المواضع الفارغة فارغون أيضًا، لذا لا تضيف شيئًا. تُزار كل عقدة مرة واحدة، لذا يكون الزمن O(n)، ويُحتفظ بمستوى واحد في الذاكرة في كل مرة، أي O(w) لأعرض مستوى w.

الخوارزمية

ابدأ بقائمة تحتوي على فهرس الجذر 0.
لكل فهرس في القائمة، من اليسار إلى اليمين، دوّن موضعي الابنين: قيمة الابن إذا كان موجودًا، و-1 إذا كان الموضع فارغًا. اجمع الأبناء الموجودين للمستوى التالي.
إذا اختلف صف موضعي الأبناء عن معكوسه، فأعِد false.
انتقل إلى المستوى التالي وكرّر حتى يصبح فارغًا، ثم أعد true.

def isSymmetric(tree):
    n = len(tree)
    level = [0]  # the real nodes of one level, left to right
    while level:
        row = []  # the child spots under this level, -1 for an empty one
        next_level = []
        for i in level:
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and tree[child] != -1:
                    row.append(tree[child])
                    next_level.append(child)
                else:
                    row.append(-1)
        if row != row[::-1]:
            return False
        level = next_level
    return True

الاستدعاء الذاتي على أزواج متناظرة

الفكرة

بدلًا من مقارنة المستويات كاملةً، قارن بين شجرتين فرعيتين: الشجرة الفرعية اليسرى للجذر، التي تبدأ عند الفهرس 1، والشجرة الفرعية اليمنى، التي تبدأ عند الفهرس 2. يكون موضعان متناظرين إذا كانا فارغين، أو إذا احتوى كلاهما على القيمة نفسها وكانت أبناؤهما متقاطعة. فالابن الأيسر لأحدهما يقابل الابن الأيمن للآخر (الزوج الخارجي)، والابن الأيمن لأحدهما يقابل الابن الأيسر للآخر (الزوج الداخلي).

في المثال الأول، تقارن mirrors(1, 2) بين قيمتي 2، ثم تستدعي mirrors(3, 6) لمقارنة قيمتي 3 الخارجيتين، وmirrors(4, 5) لمقارنة قيمتي 4 الداخليتين. يجد كل استدعاء من هذين الاستدعاءين مواضع فارغة فقط أدناه، ويُرجع true. في المثال الثاني، تجد mirrors(4, 5) قيمة 3 عند الفهرس 4 تقابل موضعًا فارغًا عند الفهرس 5، فتُرجع false، وتصعد قيمة false عائدةً إلى القمة.

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

الخوارزمية

اكتب mirrors(a, b). تكون الخانة فارغة إذا كان فهرسها يتجاوز النهاية أو كانت تحتوي على -1. إذا كانت الخانتان فارغتين، فأعِد true؛ وإذا كانت إحداهما فقط فارغة، فأعِد false.
إذا اختلفت tree[a] وtree[b]، فأعِد false.
وإلا فأعِد mirrors(2*a+1, 2*b+2) وmirrors(2*a+2, 2*b+1).
أعِد mirrors(1, 2). الجذر الذي ليس له أبناء يعطي خانتين فارغتين، وهذا يعني true.

def isSymmetric(tree):
    n = len(tree)

    def mirrors(a, b):
        # Spots a and b must hold the same value, or both be empty.
        empty_a = a >= n or tree[a] == -1
        empty_b = b >= n or tree[b] == -1
        if empty_a or empty_b:
            return empty_a and empty_b
        return (tree[a] == tree[b]
                and mirrors(2 * a + 1, 2 * b + 2)   # outer pair
                and mirrors(2 * a + 2, 2 * b + 1))  # inner pair

    return mirrors(1, 2)

مكدس صريح من الأزواج المتناظرة

الفكرة

يحتاج الاستدعاء الذاتي إلى شيء واحد فقط: الأزواج التي ما زال علينا التحقق منها. احتفظ بهذه الأزواج في مكدس خاص بك، وستختفي الاستدعاءات. ابدأ بالزوج (1, 2). أخرج زوجًا من المكدس. إذا كان الموضعان فارغين، فلا يوجد شيء أسفلهما، لذا انتقل إلى التالي. إذا كان أحدهما فارغًا أو كانت القيم مختلفة، فالشجرة غير متناظرة. وإلا فأضف الزوج الخارجي (2*a+1, 2*b+2) والزوج الداخلي (2*a+2, 2*b+1) إلى المكدس.

لا يهم ترتيب التحقق من الأزواج، لأن الشجرة تكون متناظرة فقط إذا تطابق كل زوج. يوفّر المكدس ترتيبًا حسب العمق أولًا؛ أما الطابور فيوفّر ترتيبًا حسب المستوى ويؤدي الغرض نفسه. يتوقف المثال الثالث عند أول زوج غير متطابق، (3, 6)، الذي يحتوي على 5 و9.

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

الخوارزمية

أضف الزوج (1, 2) إلى المكدس.
أخرج الزوج (a, b) من المكدس. إذا كان الموضعان فارغين (الفهرس يتجاوز النهاية أو -1)، فانتقل إلى الزوج التالي.
إذا كان أحد الموضعين فقط فارغًا، أو كانت tree[a] تختلف عن tree[b]، فأعد false.
أضف (2*a+1, 2*b+2) و(2*a+2, 2*b+1) إلى المكدس.
عندما يصبح المكدس فارغًا، أعد true.

def isSymmetric(tree):
    n = len(tree)
    stack = [(1, 2)]  # pairs of spots that must mirror each other
    while stack:
        a, b = stack.pop()
        empty_a = a >= n or tree[a] == -1
        empty_b = b >= n or tree[b] == -1
        if empty_a and empty_b:
            continue
        if empty_a or empty_b or tree[a] != tree[b]:
            return False
        stack.append((2 * a + 1, 2 * b + 2))  # outer pair
        stack.append((2 * a + 2, 2 * b + 1))  # inner pair
    return True

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

تقارن معظم الإجابات الخاطئة بين الزوج الخطأ من العقد، أو تنسى أن الموضع الفارغ جزء من الشكل.

التحقق من كل شجرة فرعية بمفردها. ليس من الضروري أن تكون الشجرة الفرعية اليسرى متناظرة بحد ذاتها: في [1, 2, 2, 3, 4, 4, 3]، الشجرة الفرعية 2, 3, 4 ليست متناظرة، لكن الشجرة بأكملها متناظرة. يجب أن تكون صورتها المرآتية هي الشجرة الفرعية اليمنى.
مقابلة الأبناء بالطريقة الخاطئة. يقابل الابن الأيسر في أحد الجانبين الابن الأيمن في الجانب الآخر: (2*a+1, 2*b+2) و(2*a+2, 2*b+1)، وليس أبدًا (2*a+1, 2*b+1).
مقارنة القيم فقط. إذا حذفت المواضع الفارغة من [1, 2, 2, -1, 3, -1, 3]، ستبدو كل طبقة متطابقة في الاتجاهين، ومع ذلك فالشجرة غير متناظرة. أبقِ على -1 في صف الطبقة، أو تحقّق من فراغ الموضع عند اختبار الزوج.
القراءة بعد نهاية المصفوفة. الفهرس الذي يتجاوز نهاية المصفوفة يشير إلى موضع فارغ. تحقّق من a < n قبل قراءة tree[a]؛ فالشجرة ذات العقدة الواحدة لا تحتوي أصلًا على فهرس 1 أو 2.
التوقف عند أول زوج متطابق. لا يثبت الزوج الجيد شيئًا؛ أرجِع true فقط بعد التحقق من كل زوج.
الخلط بين الإزاحة في Lua وR، حيث تبدأ المصفوفات من 1. أبقِ فهارس العقد بدءًا من 0 عند استخدام العملية الحسابية 2*i+1، واقرأ tree[i + 1].

أسئلة شائعة4

ما التعقيد الزمني للشجرة المتماثلة؟

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

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

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

ما الفرق بين شجرة متناظرة وشجرتين متطابقتين؟

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

هل تكون الشجرة التي تحتوي على عقدة واحدة متماثلة؟

نعم. تحتوي العقدة الواحدة على موضعين فارغين للابنين، وهذان الموضعان الفارغان متناظران. لا تكون العقدة الجذرية التي لها ابن واحد بالضبط متناظرةً أبدًا، لأن هذا الابن يقابل موضعًا فارغًا.

Python

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

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

الحالة 1

الحالة 2

الحالة 3

المدخلات

tree = [1, 2, 2, 3, 4, 4, 3]

المتوقع

true

Symmetric Tree

الدالة

القيود

أمثلة

تلميحات

الحل

قارن كل مستوى بنسخته المعكوسة

الاستدعاء الذاتي على أزواج متناظرة

مكدس صريح من الأزواج المتناظرة

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

أسئلة شائعة4

مسائل مشابهة