Subtree of Another Tree
لديك شجرتان ثنائيتان، root وsubRoot، مخزنتان كلتاهما في مصفوفة بترتيب المستويات: الجذر عند الفهرس 0، وأبناء الفهرس i عند 2*i+1 (الأيسر) و2*i+2 (الأيمن)، وتُمثّل -1 الموضع الفارغ. قد تنتهي المصفوفة بعناصر إضافية قيمتها -1.
أعِد true إذا كان لبعض عقد root، مع جميع أحفادها، الشكل والقيم نفسيهما تمامًا كما في subRoot، وأعِد false خلاف ذلك. ويُحتسب root بأكملها أيضًا.
الدالة
- rootinteger-array
- الشجرة المراد البحث فيها، بترتيب المستويات مع استخدام -1 للدلالة على موضع فارغ
- subRootinteger-array
- الشجرة المراد البحث عنها، بالتنسيق نفسه
- تُرجعboolean
- صحيح إذا ظهر subRoot في root كعقدة مع جميع العقد المتفرعة منها، وخطأ خلاف ذلك
القيود
1 ≤ root.length ≤ 32767و1 ≤ subRoot.length ≤ 32767- كل مُدخل هو
-1أو قيمة من0إلى104. root[0]وsubRoot[0]لا تكونان أبدًا-1، لذا تحتوي كلتا الشجرتين على عقدة واحدة على الأقل.- قد تنتهي أيٌّ من المصفوفتين بعناصر إضافية من
-1بعد آخر عقدة فيها. - ابنا الموضع الفارغ كلاهما فارغان أيضًا، وعمق كل شجرة لا يتجاوز
14. - قد تتكرر القيم.
أمثلة
- المدخلات
- root = [6, 2, 8, 1, 3, -1, 9]subRoot = [2, 1, 3]
- المخرجات
- true
- الشرح
- العقدة
2عند الفهرس1لها الابنان1و3، وكلاهما ورقتان. وهذا هو بالضبطsubRoot.
- المدخلات
- root = [6, 2, 8, 1, 3, -1, 9, -1, -1, 0]subRoot = [2, 1, 3]
- المخرجات
- false
- الشرح
- أصبح للعنصر
3الموجود أسفل العقدة2الآن ابنٌ هو0. تأخذ الشجرة الفرعية كل نسلها، لذا تضم العقدة2أربع عقد مقابل ثلاث عقد فيsubRoot، ولا تحتوي أي عقدة أخرى على2.
- المدخلات
- root = [5, 5, 7]subRoot = [5]
- المخرجات
- true
- الشرح
- للعقدة الجذرية
5ابنان، لذا فهي لا تطابق العقدة المفردة5. أما5عند الفهرس1فهي ورقة وتطابق.
سؤال إضافي
هل يمكنك إنشاء بصمة لكل شجرة فرعية اعتمادًا على قيمتها وبصمتي الشجرتين الفرعيتين التابعتين لها، بحيث لا تستغرق مقارنتها مع subRoot سوى O(1)؟ ماذا تفعل عندما تتصادم بصمتا شجرتين فرعيتين مختلفتين؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
إذا ظهرت
subRootداخلroot، فسيكون أعلاها على إحدى عقدroot. ما العقد التي يمكن أن تكون هذه، وما الذي تتحقق منه عندها؟اكتب دالة تحدد ما إذا كانت شجرتان متطابقتين: كلتاهما فارغتان، أو لهما القيمة نفسها في الأعلى مع تطابق الشجرتين الفرعيتين اليسرى واليمنى. إذا كان أحد الموضعين فارغًا والآخر يحتوي على عقدة فعلية، فهما مختلفتان.
أجرِ هذا الفحص انطلاقًا من كل عقدة في
root. لتجاوز معظمها، احسب ارتفاع كل عقدة أولًا: لا يمكن أن تتطابق إلا عقدة يساوي ارتفاعها ارتفاعsubRoot.
الحل
تتكوّن المسألة من جزأين: تحديد ما إذا كانت شجرتان متطابقتين، واختيار الموضع الذي نجري فيه هذا الفحص داخل root. لا يمكن أن تطابق إلا عقدةٌ يساوي ارتفاعُها ارتفاعَ subRoot، وبما أن العقد ذات الارتفاع نفسه لا تتداخل، فإن فحص هذه العقد فقط يمرّ على كل عقدة في root مرة واحدة على الأكثر.
قارن عند كل عقدة
الفكرة
تكون الخانة i حقيقية عندما تكون i داخل المصفوفة وتكون القيمة فيها ليست -1. تكون شجرتان متطابقتين عندما تكونان فارغتين، أو عندما تحتوي قمتهما على القيمة نفسها وتكون شجرتاهما الفرعيتان اليسرى واليمنى متطابقتين. تتنقّل same(i, j) في root بدءًا من i وفي subRoot بدءًا من j بالتزامن. إذا ظهرت subRoot داخل root، فستكون قمتها على إحدى العقد، لذا جرّب same(i, 0) بدءًا من كل i حقيقية.
قد تستمر المطابقة الجزئية حتى m خطوة قبل أن تفشل، وذلك بدءًا من كل واحدة من n عقد: O(n·m). هنا يحدّ الحد الأقصى للعمق من ذلك: لا تمرّ على العقدة إلا الفحوص التي تبدأ منها أو من عقدة أعلى منها، وبحد أقصى 14.
الخوارزمية
- اكتب
same(i, j). إذا كان الموضعiفيrootوالموضعjفيsubRootفارغين، فأعِدtrue؛ وإذا كان أحدهما فقط فارغًا، فأعِدfalse. - إذا اختلفت القيمتان، فأعِد
false. وإلا فأعِدsame(2*i+1, 2*j+1)وsame(2*i+2, 2*j+2). - أعِد
trueإذا تحققsame(i, 0)لبعض الفهارس الحقيقيةiفيroot، وfalseخلاف ذلك.
def isSubtree(root, subRoot):
n, m = len(root), len(subRoot)
def same(i, j):
# True if the subtree at root[i] equals the subtree at subRoot[j].
a = i < n and root[i] != -1
b = j < m and subRoot[j] != -1
if not a or not b:
return a == b # two empty spots match, one empty spot does not
if root[i] != subRoot[j]:
return False
return same(2 * i + 1, 2 * j + 1) and same(2 * i + 2, 2 * j + 2)
# Try every real node of root as the top of a match.
for i in range(n):
if root[i] != -1 and same(i, 0):
return True
return Falseقارن فقط عندما تكون الارتفاعات متساوية
الفكرة
الأشجار المتطابقة لها الارتفاع نفسه، ويُحسب الارتفاع بعدد العقد على أطول مسار إلى الأسفل. لذلك لا يستحق الفحص سوى العقد في root التي يساوي ارتفاعها ارتفاع subRoot. في المثال الأول، ارتفاع subRoot هو 2، وفي root لا ينطبق ذلك إلا على العقدتين 2 و8.
تكون العقدة أطول من كل عقدة أسفلها، لذا لا تكون عقدتان متساويتان في الارتفاع إحداهما داخل الأخرى. يفحص كل تحقق الشجرة الفرعية للعقدة التي يبدأ منها فقط، لذا لا تمر عمليات التحقق مجتمعة على كل عقدة في root أكثر من مرة.
تقع الأبناء عند فهارس أكبر من فهرس العقدة الأم، لذا فإن المسح من آخر فهرس إلى الأول يصل إلى كلا الابنين قبل العقدة الأم. يستغرق مسحا الارتفاع وعمليات التحقق وقتًا قدره O(n + m).
الخوارزمية
- املأ مصفوفة ارتفاع لكل شجرة، مع المسح من الفهرس الأخير نزولًا إلى
0: يحصل الموضع الفارغ على0، وتحصل العقدة الفعلية على1مضافًا إليها الارتفاع الأكبر لطفليها. - لكل فهرس
iفيrootيساوي ارتفاعه الارتفاع عند الفهرس0فيsubRoot، شغّلsame(i, 0)وأعِدtrueإذا تحقق ذلك. - أعِد
false.
def isSubtree(root, subRoot):
n, m = len(root), len(subRoot)
def same(i, j):
# True if the subtree at root[i] equals the subtree at subRoot[j].
a = i < n and root[i] != -1
b = j < m and subRoot[j] != -1
if not a or not b:
return a == b # two empty spots match, one empty spot does not
if root[i] != subRoot[j]:
return False
return same(2 * i + 1, 2 * j + 1) and same(2 * i + 2, 2 * j + 2)
def heights(tree):
# Children sit at larger indexes, so a backward scan finishes them first.
h = [0] * len(tree)
for i in range(len(tree) - 1, -1, -1):
if tree[i] != -1:
left = h[2 * i + 1] if 2 * i + 1 < len(tree) else 0
right = h[2 * i + 2] if 2 * i + 2 < len(tree) else 0
h[i] = 1 + max(left, right)
return h
target = heights(subRoot)[0]
rootHeights = heights(root)
# Only a node of the same height can match, and no two such nodes overlap.
for i in range(n):
if rootHeights[i] == target and same(i, 0):
return True
return False
أخطاء شائعة وحالات حدّية
- قبول تطابق جزئي، كما في المثال الثاني. يجب أن تفشل
sameعندما تحتويrootعلى عقدة في موضع فارغ فيsubRoot. - التوقف عند أول عقدة ذات القيمة الصحيحة. في المثال الثالث، لا يتطابق الجذر
5، بينما تتطابق الورقة5الموجودة تحته. - مقارنة أجزاء المصفوفتين. تنتشر عقد الشجرة الفرعية على مستويات عديدة، وقد تنتهي أي من المصفوفتين بعناصر إضافية
-1. والفهرس الذي يتجاوز نهاية المصفوفة يُعدّ موضعًا فارغًا، مثل-1. - في Lua وR، أبقِ فهارس العقد تبدأ من 0 لحساب
2*i+1، واقرأroot[i + 1].
أسئلة شائعة3
ما هو التعقيد الزمني لمسألة الشجرة الفرعية لشجرة أخرى؟
تكلّف المقارنة انطلاقًا من كل عقدة O(n·m) في أسوأ الحالات، حيث يمثّل n وm حجمي الشجرتين. وتصبح المقارنة عند العقد التي يساوي ارتفاعها ارتفاع subRoot فقط بتعقيد O(n + m)، لأن كل عقدة في root يُمرّ عليها عندئذٍ مرة واحدة على الأكثر.
هل يمكن حل مسألة الشجرة الفرعية لشجرة أخرى باستخدام مطابقة السلاسل النصية؟
نعم. اكتب كل شجرة بترتيب المرور السابق، مع استخدام # لكل ابن فارغ وفاصل قبل كل قيمة: ,2,1,#,#,3,#,#. تكون subRoot شجرة فرعية بالضبط عندما تظهر سلسلتها داخل سلسلة root، وتجدها KMP في O(n + m). من دون العلامات، تعطي الأشكال المختلفة السلسلة نفسها؛ ومن دون الفواصل، تحتوي 12 على 2.
هل تُحتسب العقدة التي تطابق subRoot لكنها تحتوي على أبناء إضافيين؟
لا. الشجرة الفرعية هي عقدة مع جميع العقد المتحدرة منها، لذا يجب أن تظهر أيضًا كل عقدة أسفل العقدة المطابقة في subRoot. في المثال الثاني، تجعل العقدة الإضافية 0 أسفل 3 الإجابة false.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def isSubtree(root, subRoot):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
الوسائط
root = [6, 2, 8, 1, 3, -1, 9] subRoot = [2, 1, 3]
الإخراج المتوقع
true