Lowest Common Ancestor of a Binary Tree
لديك شجرة ثنائية في المصفوفة root، بترتيب الكومة: الجذر عند الفهرس 0، وأبناء الفهرس i عند 2*i+1 (الأيسر) و2*i+2 (الأيمن)، وتُستخدم القيمة -1 للدلالة على موضع فارغ. القيم متميزة ولا تتبع أي ترتيب.
أعِد قيمة أدنى سلف مشترك للعقدتين p وq، وهما قيمتان لعقدتين مختلفتين: أعمق عقدة تحتوي شجرتها الفرعية على كلتيهما. تشمل الشجرة الفرعية عقدتها العليا، لذا إذا كانت q تقع أسفل p، فالإجابة هي p.
الدالة
- rootinteger-array
- الشجرة الثنائية بترتيب المستويات، مع استخدام -1 للدلالة على موضع فارغ
- pinteger
- قيمة عقدة واحدة
- qinteger
- قيمة عقدة أخرى
- تُرجعinteger
- قيمة أدنى عقدة تحتوي شجرتها الفرعية على كلٍّ من p وq
القيود
2 ≤ root.length ≤ 32767- كل
root[i]إما-1أو قيمة تحقق0 ≤ root[i] ≤ 104. root[0]لا تكون أبدًا-1، والشجرة تحتوي على عقدتين على الأقل.- قد تنتهي المصفوفة بعناصر
-1إضافية بعد العقدة الأخيرة. - كلا ابني الموضع الفارغ فارغان أيضًا، والعمق لا يتجاوز
14. - جميع القيم في الشجرة مختلفة، ولا تتبع أي ترتيب.
- تمثل
pوqقيمتين لعقدتين مختلفتين في الشجرة، بأي ترتيب.
أمثلة
- المدخلات
- root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]p = 6q = 9
- المخرجات
- 3
- الشرح
6هو الابن الأيسر لـ3، وتقع9أسفل4إلى يمين3، لذا يلتقيان عند3. ستشير مقارنة القيم إلى الجذر8:6أصغر و9أكبر.
- المدخلات
- root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]p = 4q = 7
- المخرجات
- 4
- الشرح
7هو الابن الأيسر لـ4، وتشمل الشجرة الفرعية لـ4العقدة4نفسها، لذا فالإجابة هي4.
- المدخلات
- root = [1, -1, 6, -1, -1, 3, 0, -1, -1, -1, -1, -1, -1, -1, -1]p = 3q = 0
- المخرجات
- 6
- الشرح
- الجذر
1ليس له ابن أيسر. ابنه الأيمن6له3على يساره و0على يمينه، لذا تلتقي القيم عند6.
سؤال إضافي
إذا كان من الممكن غياب p أو q، وكانت الإجابة -1، فأي اختصار في المرور الواحد يفشل، وكيف يمكنك مع ذلك إنهاء المهمة في اجتياز واحد؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
جرّب قاعدة شجرة البحث على المثال الأول:
6أصغر من الجذر8و9أكبر منه. أين يقعان فعليًا؟ ماذا يخبرك ذلك عن مقارنة القيم في هذه الشجرة؟لتُخبر كل شجرة فرعية عقدتها الأم بما وجدته: لا شيء، أو إحدى القيمتين، أو الإجابة. والعقدة التي تسمع عن قيمة من كلا ابنيها هي الموضع الذي يلتقي فيه
pوq.اكتب دالة递归
find(i)تُعيد-1للمكان الفارغ، وiعندما تكونroot[i]هيpأوq، وiعندما تُعيد العقدتان الابنتان فهرسًا، وإلا فأعِد نتيجة الابن التي لا تساوي-1. الإجابة هيroot[find(0)].
الحل
لا يحدد الترتيب أي جانب يحتوي على قيمة، لذا عليك أن تتحقق. تتيح لك عملية اجتياز واحدة بترتيب لاحق أن تُبلغ كل شجرة فرعية عمّا وجدته، وتلتقي القيم عند أول عقدة تسمع من كلا الجانبين.
انزل إلى الأسفل، وابحث في كل جانب
الفكرة
انزل من الجذر، وابحث في كل عقدة عن p وعن q في الشجرة الفرعية اليسرى. إذا وُجدا كلاهما هناك، فاتجه يسارًا. إذا لم يوجد أيٌّ منهما، فاتجه يمينًا. إذا وُجد أحدهما في كل جهة، فهذا يعني أن القيمتين تنفصلان، وتكون هذه العقدة هي الإجابة. والعقدة التي تحتوي على p أو q هي الإجابة أيضًا، لأن القيمة الأخرى لا بد أن تكون أسفلها. بالنسبة إلى 6 و9، يجد الجذر كليهما في جهته اليسرى، وعند 3، تحتوي العقدة الوحيدة التي تضم 6 على p فقط.
تبحث كل خطوة نزولًا في شجرة فرعية كاملة، لذا تكلّف المستويات h مقدار O(n·h)، وتكون الكلفة O(n²) في شجرة طويلة وضيقة بلا حدّ للعمق. وقد زار البحث عند 8 كل عقدة أسفل 3 بالفعل، ثم تزور خطوة 3 بعض العقد مرة أخرى.
الخوارزمية
- اكتب
contains(i, value):falseإذا كان الموضع فارغًا (بعد النهاية أو-1)، وtrueإذا كانتroot[i]تساويvalue، وإلا فاسأل كلا الابنين. - ابدأ عند
i = 0. إذا كانتroot[i]هيpأوq، فأعِدها. - إذا كان الفرع الأيسر عند
2*i+1يحتوي على القيمتين، فانتقل إليه. وإذا لم يكن يحتوي على أيٍّ منهما، فانتقل إلى2*i+2. - وإلا فأعِد
root[i].
def lowestCommonAncestor(root, p, q):
n = len(root)
def contains(i, value):
# Is value somewhere in the subtree at index i?
if i >= n or root[i] == -1:
return False
if root[i] == value:
return True
return contains(2 * i + 1, value) or contains(2 * i + 2, value)
i = 0 # p and q are always inside the subtree at i
while True:
if root[i] == p or root[i] == q:
return root[i] # one value is here, the other is below it
left = 2 * i + 1
p_left = contains(left, p)
q_left = contains(left, q)
if p_left and q_left:
i = left # both on the left
elif not p_left and not q_left:
i = 2 * i + 2 # both on the right
else:
return root[i] # one on each sideمرور واحد بترتيب ما بعدي
الفكرة
اجعل كل شجرة فرعية تُجيب مرة واحدة، بدءًا من الأسفل إلى الأعلى. تُعيد find(i) فهرس الإجابة إذا كانت الشجرة الفرعية عند i تحتوي على القيمتين، وفهرس p أو q إذا كانت تحتوي على إحداهما، و-1 إذا لم تكن تحتوي على أيٍّ منهما.
تُعيد العقدة التي تحتوي على p أو q فهرسها الخاص من دون النظر إلى ما تحتها. إذا كانت القيمة الأخرى في شجرتها الفرعية، فهذه العقدة هي الإجابة؛ وإلا، تتلقى عقدة أعلى منها نتيجة من الجانبين. أما أي عقدة أخرى، فتسأل طفليها. تعني النتيجتان أن القيمتين وصلتا من جانبين مختلفين والتقتا هنا. وتنتقل النتيجة الوحيدة إلى الأعلى كما هي، سواء أكانت تمثل قيمة واحدة أم الإجابة النهائية.
في المثال الأول، تحصل 3 على الفهرس 3 من يسارها وعلى 10 من يمينها، ثم تُعيد فهرسها الخاص 1، وتمرره الجذر إلى الأعلى. تُزار كل عقدة مرة واحدة: زمن O(n)، واستدعاء递归 O(h).
الخوارزمية
- تعطي
find(i)القيمة-1إذا كان الفهرس يتجاوز النهاية أو كان-1. - تعطي العقدة التي تكون قيمتها
pأوqالقيمةiدون البحث في الأسفل. - تحسب أي عقدة أخرى
left = find(2*i+1)وright = find(2*i+2). إذا لم تكن أيٌّ منهما-1، فتعطيi؛ وإلا فتعطي القيمة التي ليست-1، أو-1. - أعِد
root[find(0)].
def lowestCommonAncestor(root, p, q):
n = len(root)
def find(i):
# In the subtree at index i: the index of the answer if both values are
# inside, the index of the one that is, or -1 when neither is.
if i >= n or root[i] == -1:
return -1
if root[i] == p or root[i] == q:
return i
left = find(2 * i + 1)
right = find(2 * i + 2)
if left != -1 and right != -1:
return i # one value on each side: this node is the answer
return left if left != -1 else right
return root[find(0)]
أخطاء شائعة وحالات حدّية
- مقارنة القيم بالعقدة. الشجرة ليس لها ترتيب: في المثال الأول، يتوقف الاجتياز عند الجذر
8بدلًا من3. - إرجاع
trueأوfalseبدلًا من فهرس. لا يستطيع الوالد معرفة ما إذا كانت الإجابة النهائية موجودة تحته بالفعل. - قراءة ابن دون التحقق من الطول. للعقدة
9عند الفهرس10فهرسا ابنَين هما21و22، وهما بعد آخر عنصر. - إرجاع
find(0)، وهو فهرس، بدلًا منroot[find(0)]. - في Lua وR، تبدأ المصفوفات من 1: أبقِ فهارس العقد بدءًا من 0، واقرأ
root[i + 1].
أسئلة شائعة3
ما التعقيد الزمني لإيجاد السلف المشترك الأدنى في شجرة ثنائية؟
تمرّ عملية الاجتياز اللاحق بكل عقدة مرة واحدة على الأكثر: زمن O(n). يحتوي مكدس الاستدعاءات التكرارية على إطار واحد لكل مستوى، لذا تكون المساحة O(log n) في شجرة متوازنة وO(n) في شجرة على شكل مسار.
ما الفرق بين هذا وبين أدنى سلف مشترك في شجرة بحث ثنائية؟
في شجرة بحث، تخبرك مقارنة p وq بعقدةٍ ما بأي جانب يقع كلٌّ منهما، لذا يعثر مسار واحد من الجذر على الإجابة في O(h). أما هنا، فلا تخبرك المقارنة بشيء، لذا تبحث في الأشجار الفرعية.
هل يمكنك إيجاد أقرب سلف مشترك باستخدام مؤشرات الوالد؟
نعم. في هذه المصفوفة، يكون والد الفهرس i هو (i-1)/2 بعد التقريب إلى الأسفل. انقل الفهرس الأكبر من الفهرسين إلى والده حتى يتساويا؛ فالفهرس الأكبر لا يكون أبدًا سلفًا لفهرس أصغر. مع العقد المرتبطة، ضع أسلاف p في مجموعة، واصعد من q إلى أول عقدة منها تظهر في المجموعة.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def lowestCommonAncestor(root, p, q):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
الوسائط
root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9] p = 6 q = 9
الإخراج المتوقع
3