Lowest Common Ancestor of a BST
لديك شجرة بحث ثنائية مخزنة في المصفوفة tree بترتيب المستويات، وقيمتان p وq تظهران فيها كلتاهما. يقع الجذر عند الفهرس 0، ويقع ابنا العقدة عند الفهرس i عند 2*i+1 (الأيسر) و2*i+2 (الأيمن)، وتشير -1 إلى موضع فارغ، وقد تنتهي المصفوفة بإدخالات إضافية من -1. في شجرة البحث الثنائية، تكون كل قيمة في الشجرة الفرعية اليسرى للعقدة أصغر من قيمة العقدة، وتكون كل قيمة في شجرتها الفرعية اليمنى أكبر منها.
اكتب دالة باسم lowestCommonAncestor تُرجع قيمة أدنى سلف مشترك لكل من p وq: أي أعمق عقدة تضم كليهما في شجرتها الفرعية. تُعد العقدة جزءًا من شجرتها الفرعية، لذا إذا كانت p تقع أعلى q، فستكون الإجابة هي p نفسها.
الدالة
- treeinteger-array
- شجرة البحث الثنائية بترتيب المستويات، مع استخدام -1 للدلالة على موضع فارغ
- pinteger
- القيمة الأولى المطلوب العثور عليها
- qinteger
- القيمة الثانية المراد العثور عليها
- تُرجعinteger
- قيمة أعمق عقدة يكون كلٌّ من p وq ضمن شجرتها الفرعية
القيود
1 ≤ tree.length ≤ 32767- كل عنصر
tree[i]إما-1أو قيمة تحقق0 ≤ tree[i] ≤ 105. tree[0]لا يكون أبدًا-1، لذا تحتوي الشجرة على عقدة واحدة على الأقل.- قد تنتهي المصفوفة بإدخالات
-1إضافية بعد العقدة الأخيرة. - كلا الفرعين في الموضع الفارغ فارغان أيضًا، والعمق لا يزيد على
14. - الشجرة هي شجرة بحث ثنائية صالحة، لذا فجميع قيمها متميزة.
pوqهما قيم عقد في الشجرة. قد يأتيان بأي ترتيب وقد يكونان متساويين.
أمثلة
- المدخلات
- tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 3q = 15
- المخرجات
- 8
- الشرح
- العقدة
3هي الابن الأيسر للعقدة8، وتقع العقدة15أسفل العقدة12وعلى يمين العقدة8. عند الصعود من كل منهما، تكون أول عقدة يصلان إليها معًا هي8، لذا فهذه هي الإجابة؛ والعقدة الجذر20هي أيضًا سلف مشترك، لكنها أعلى منهما.
- المدخلات
- tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 12q = 10
- المخرجات
- 12
- الشرح
- العقدة
10هي الابن الأيسر للعقدة12. تُعدّ العقدة سلفًا لنفسها، لذا تحتوي الشجرة الفرعية للعقدة12على القيمتين، ولا تحتوي أي عقدة أسفلها عليهما: الإجابة هي12. قد تأتي القيم بأي ترتيب؛ هناpهي الأكبر.
- المدخلات
- tree = [50, 30, 70, 20, 40, 60, 80, -1, -1, -1, -1, 55]p = 55q = 80
- المخرجات
- 70
- الشرح
- كلٌّ من
55و80أكبر من الجذر50، لذا يقع كلاهما على يمينه. عند70يفترق مسارهما:55أصغر ويقع على اليسار (أسفل60)، و80أكبر ويقع على اليمين. لذا فإن70هو الجواب.
+12 اختبارات مخفية عند الإرسال
سؤال إضافي
ما الذي ستغيّره إذا كان من المحتمل ألّا تكون p أو q موجودة في الشجرة، وكان على الدالة أن تُرجع -1 في هذه الحالة؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
قف عند الجذر. إذا كانت قيمة كلٍّ من
pوqأصغر من قيمته، ففي أي شجرة فرعية توجد العقدتان؟ما دامت القيمتان على الجانب نفسه من العقدة الحالية، فسيكون كل سلف مشترك أعمق منها على ذلك الجانب أيضًا. أول عقدة لا تكونان على الجانب نفسه منها، أو تحتوي على إحداهما، هي العقدة التي تبحث عنها.
ابدأ عند الفهرس
0. طالما أن القيمتين أصغر منtree[i]، انتقل إلى2*i+1؛ وطالما أن القيمتين أكبر، انتقل إلى2*i+2. وإلا فأعِدtree[i].
الحل
في شجرة ثنائية عادية، لا يمكنك معرفة مكان وجود قيمة من دون البحث في جانبي كل عقدة. تخبرك شجرة البحث عند كل عقدة بأن القيم الأصغر تقع على اليسار، والأكبر على اليمين. لذا ابدأ من الجذر وتقدّم نحو الجانب الذي توجد فيه القيمتان. أول عقدة لا تعودان عندها في الجانب نفسه هي الإجابة، ويمكنك العثور عليها باتباع مسار واحد، من دون النظر إلى بقية الشجرة.
ابحث في الشجرة بأكملها، متجاهلًا الترتيب
الفكرة
أولًا، كيفية التنقّل في المصفوفة. العقدة عند الفهرس i لها ابن أيسر عند 2*i+1 وابن أيمن عند 2*i+2. لا يكون الابن موجودًا فعليًا إلا إذا كان فهرسه ضمن حدود المصفوفة وكانت القيمة هناك لا تساوي -1. في [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]، للعقدة الجذرية 20 العقدتان 8 و31 عند الفهرسين 1 و2، وللعقدة 12 عند الفهرس 4 العقدتان 10 و15 عند الفهرسين 9 و10.
تعمل هذه الطريقة الأولى مع أي شجرة ثنائية. تعرض الدالة العودية find(i) محتويات الشجرة الفرعية عند i. ويُبلّغ عن الموضع الفارغ بالقيمة -1. أما العقدة التي تحتوي على p أو q فتُبلغ عن نفسها: فإما أن تكون القيمة الأخرى أسفلها، وعندها تكون هي الإجابة، أو تكون القيمة الأخرى في موضع آخر، وعندها ستعثر عقدة أعلى منها على القيمتين. وفي غير ذلك، تستعلم العقدة من ابنيها. إذا أبلغ كلا الجانبين عن شيء ما، فهذا يعني أن p في أحد الجانبين وq في الجانب الآخر، لذا تكون هذه العقدة هي موضع التقائهما. وإذا أبلغ جانب واحد فقط عن شيء ما، فمرّر ذلك إلى الأعلى.
عندما تكون p = 3 وq = 15، تحصل العقدة 8 على الفهرس 3 من ابنها الأيسر وعلى الفهرس 10 من ابنها الأيمن، لذا تُبلغ عن نفسها. وتتلقى العقدة الجذرية ذلك من ابنها الأيسر و-1 من ابنها الأيمن، ثم تمرّر 8 إلى الأعلى.
هذه الطريقة صحيحة، لكنها قد تزور كل العقد، بزمن O(n)، وبمساحة O(h) للاستدعاء العودي. وهي لا تستخدم ترتيب القيم مطلقًا، مع أن هذا هو جوهر شجرة البحث.
الخوارزمية
- اكتب
find(i). إذا كان الموضع عندiفارغًا (بعد النهاية أو-1)، فأعِد-1. - إذا كانت
tree[i]هيpأوq، فأعِدi. - استدعِ
findعلى2*i+1و2*i+2. إذا عُثر على شيء في كليهما، فأعِدi. - وإلا فأعِد الجانب الذي عُثر فيه على شيء، أو
-1. - أعِد
tree[find(0)].
def lowestCommonAncestor(tree, p, q):
n = len(tree)
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 tree[i] == -1:
return -1
if tree[i] == p or tree[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 tree[find(0)]قارن بين مساري البحث
الفكرة
استخدم الآن الترتيب. يمكنك العثور على قيمة بالطريقة التي يُفترض أن تُجرى بها عملية البحث في شجرة البحث: ابدأ من الجذر، واتجه يسارًا عندما تكون القيمة أصغر من العقدة، ويمينًا عندما تكون أكبر منها، وتوقف عندما تصل إليها. يمر هذا المسار عبر كل أسلاف القيمة ولا يمر بأي شيء آخر، لأن المسار من الجذر إلى أي عقدة فريد.
سجّل مسار p ومسار q. يبدأ كلاهما من الجذر ويتبعان العقد نفسها حتى تسلك القيمتان اتجاهين مختلفين. يمثّل الجزء المشترك في البداية قائمة أسلافهما المشتركين، لذا فإن آخر قيمة مشتركة هي الأدنى. بالنسبة إلى 3 و15، يكون المساران 20, 8, 3 و20, 8, 12, 15: وهما يشتركان في 20, 8، والإجابة هي 8. وبالنسبة إلى 12 و10، فهما 20, 8, 12 و20, 8, 12, 10، والإجابة هي 12.
تستغرق كل رحلة خطوة واحدة لكل مستوى، لذا يكون الزمن O(h)، وبحد أقصى 14 خطوة هنا، مهما كان عدد العقد في الشجرة. تتطلب القائمتان مساحة O(h).
الخوارزمية
- اكتب
path(target): ابدأ عند الفهرس0، وسجّلtree[i]، وتوقّف عندما يساويtarget، وإلا فانتقل إلى2*i+1إذا كانtargetأصغر، وإلى2*i+2إذا كان أكبر. - أنشئ المسار إلى
pوالمسار إلىq. - تتبّع القائمتين من البداية ما دامت قيمهما متطابقة، مع تذكّر آخر تطابق.
- أعِد آخر قيمة مشتركة.
def lowestCommonAncestor(tree, p, q):
def path(target):
# The values met on the way from the root down to target.
values = []
i = 0
while True:
values.append(tree[i])
if tree[i] == target:
return values
i = 2 * i + 1 if target < tree[i] else 2 * i + 2
to_p, to_q = path(p), path(q)
# Both paths start at the root; the answer is the last value they share.
answer = to_p[0]
for a, b in zip(to_p, to_q):
if a != b:
break
answer = a
return answerتابع النزول حتى تنقسم القيم
الفكرة
يتفق المساران ما دام p وq يسيران في الاتجاه نفسه، لذا لا تحتاج إلى تخزينهما. سر في المسارين معًا. عند عقدة تحمل v، إذا كانت القيمتان أصغر من v، فكلتاهما في الفرع الأيسر، وكذلك كل سلف مشترك يقع أسفل v: انتقل إلى اليسار. وإذا كانتا أكبر، فانتقل إلى اليمين.
وإلا فقد وصلت. إما أن تكون إحدى القيمتين أصغر من v والأخرى أكبر، فتقعان في فرعين مختلفين ولا تحتوي أي عقدة فرعية لـ v عليهما معًا؛ أو أن تكون إحداهما مساوية لـ v، فالعقدة سلفٌ لنفسها. في كلتا الحالتين، تكون v أعمق عقدة تقع فوقهما معًا.
في المثال الثالث، يكون الجذر 50 أصغر من كل من 55 و80، لذا تنتقل إلى اليمين نحو 70. هناك، تكون 55 أصغر و80 أكبر: الإجابة هي 70. في المثال الثاني، تنتقل من 20 إلى 8 ثم إلى 12، التي تساوي p، وتتوقف.
تتبع مسارًا واحدًا من الجذر، مع زوج واحد من المقارنات في كل مستوى، لذا فالزمن هو O(h) والمساحة هي O(1). ولا تتم قراءة أي جزء آخر من الشجرة.
الخوارزمية
- ابدأ عند الفهرس
i = 0. - اقرأ
v = tree[i]. - إذا كان
p < vوq < v، فانتقل إلى2*i+1وكرّر. - إذا كان
p > vوq > v، فانتقل إلى2*i+2وكرّر. - وإلا فأعِد
v.
def lowestCommonAncestor(tree, p, q):
i = 0 # start at the root
while True:
value = tree[i]
if p < value and q < value:
i = 2 * i + 1 # both are smaller: the answer is on the left
elif p > value and q > value:
i = 2 * i + 2 # both are larger: the answer is on the right
else:
return value # they split here, or one of them is this node
أخطاء شائعة وحالات حدّية
المسار قصير، لذا تنشأ معظم الأخطاء من قاعدة التوقف.
- استخدام
≤و≥في اختبارات الحركة. عندما تكونp = 12وq = 10، فإن الاختبارp ≤ 12وq ≤ 12يتجاوز الإجابة إلى10، ومن هناك يعيد المسار10أو يخرج من الشجرة. تحرّك فقط عندما تكون القيمتان كلتاهما على جانب واحد بصرامة. - افتراض أن
p < q. قد تأتي القيم بأي ترتيب. اختبر كلتيهما بالنسبة إلى العقدة، أو بدّلهما أولًا بحيث تكونpهي الأصغر. - نسيان أن إحدى القيمتين قد تكون سلفًا للأخرى. عندئذٍ تكون الإجابة هي تلك القيمة نفسها، لا والدها.
- إرجاع الفهرس بدلًا من القيمة. تعيد الدالة
tree[i]، لاi. - البحث في الشجرة كلها. يعطي الإجابة الصحيحة، لكنه يزور كل العقد تقريبًا، بينما يكفي اتباع مسار واحد.
- الخلط بين الإزاحة في Lua وR، حيث تبدأ المصفوفات من 1. أبقِ فهارس العقد تبدأ من 0 لإجراء الحساب
2*i+1، واقرأtree[i + 1].
أسئلة شائعة4
ما هو التعقيد الزمني لإيجاد السلف المشترك الأدنى في شجرة بحث ثنائية؟
يتبع المسار من الجذر مسارًا واحدًا، لذا يستغرق O(h) من الوقت لشجرة عمقها h، وO(1) من المساحة الإضافية. في شجرة متوازنة يكون ذلك O(log n)؛ أما في شجرة على شكل مسار واحد، فيكون O(n).
كيف يختلف LCA في شجرة بحث ثنائية عن LCA في شجرة ثنائية؟
في شجرة ثنائية عادية، يمكن أن توجد القيمة في أي مكان، لذا تبحث في الشجرتين الفرعيتين لكل عقدة، ويكون مقدار العمل O(n). أما في شجرة البحث، فإن مقارنة القيمتين بقيمة العقدة تخبرك بأي جانب توجد كل منهما، لذا تتبع مسارًا واحدًا من الجذر. تظل طريقة الشجرة العامة التكرارية صالحة لشجرة البحث، لكنها تهدر تلك المعلومات.
هل يمكن أن تكون العقدة هي نفسها السلف المشترك الأقرب لها؟
نعم. تُعَدّ العقدة سلفًا لنفسها، لذا عندما تكون p أعلى من q، تكون الإجابة هي p. وتعطي القاعدة نفسها p عندما تكون القيمتان متساويتين. تتعامل عملية السير مع الحالتين: إذ تتوقف بمجرد أن تساوي العقدة الحالية إحدى القيمتين.
لماذا يتوقف المسار عند أول عقدة ينفصل عندها p وq؟
عند تلك العقدة، تكون إحدى القيمتين أصغر والأخرى أكبر، لذا فهما تقعان في شجرتين فرعيتين مختلفتين. تقع كل عقدة أسفلها في واحدة فقط من هاتين الشجرتين الفرعيتين، ولا يمكنها أن تحتوي على القيمتين معًا. تحتوي عقدة التفرّع على القيمتين، ولا توجد عقدة أعمق منها تفعل ذلك، وهذا هو بالضبط تعريف السلف المشترك الأدنى.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def lowestCommonAncestor(tree, p, q):
# اكتب الشيفرة هناالحالة 1
الحالة 2
الحالة 3
المدخلات
tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15] p = 3 q = 15
المتوقع
8