Lowest Common Ancestor of a BST
لديك شجرة بحث ثنائية مخزنة بترتيب الكومة في المصفوفة tree: الجذر عند الفهرس 0، وأبناء الفهرس i عند 2*i+1 (الأيسر) و2*i+2 (الأيمن)، وتشير -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ومن15، تكون أول عقدة يصلان إليها هي8:3هو ابنها الأيسر، و15يقع أسفل12في جهتها اليمنى. الجذر20سلف مشترك أيضًا، لكنه أعلى.
- المدخلات
- tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 12q = 10
- المخرجات
- 12
- الشرح
10هو الابن الأيسر لـ12، وتُعَدّ العقدة سلفًا لنفسها، لذا تحتوي12على كلتا القيمتين، ولا يحتوي أي شيء أسفلها عليهما. هناpهي القيمة الأكبر.
- المدخلات
- tree = [50, 30, 70, 20, 40, 60, 80, -1, -1, -1, -1, 55]p = 55q = 80
- المخرجات
- 70
- الشرح
- كلتا القيمتين أكبر من الجذر
50، لذا تقعان كلتاهما على يمينه. وعند70يتفرع المساران:55أصغر ويقع على اليسار، أسفل60، و80أكبر.
سؤال إضافي
ما الذي ستغيّره إذا كان من المحتمل ألا تكون p أو q موجودة في الشجرة، وكان على الدالة أن تُرجع -1 في هذه الحالة؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
قف عند الجذر. إذا كانت قيمة كل من
pوqأصغر من قيمته، ففي أي شجرة فرعية توجد العقدتان؟ما دامت القيمتان على الجانب نفسه من العقدة الحالية، فكل سلف مشترك أعمق يقع على ذلك الجانب أيضًا. العقدة الأولى التي لا تكونان فيها على الجانب نفسه، أو التي تحتوي على إحداهما، هي العقدة التي تريدها.
ابدأ عند الفهرس
0. ما دامت القيمتان أصغر منtree[i]، انتقل إلى2*i+1؛ وما دامت القيمتان أكبر، انتقل إلى2*i+2. وإلا فأعِدtree[i].
الحل
تُبيّن لك شجرة البحث في كل عقدة أين توجد القيمة: الأصغر على اليسار، والأكبر على اليمين. ابدأ من الجذر واتجه نحو الجانب الذي يحتوي على القيمتين. أول عقدة تتوقف عندها القيمتان عن مشاركة الجانب نفسه هي الإجابة، وتصل إليها عبر مسار واحد.
ابحث في الشجرة بأكملها، متجاهلًا الترتيب
الفكرة
تعمل هذه الطريقة مع أي شجرة ثنائية. تُرجع الدالة العودية find(i) ما تحتويه الشجرة الفرعية عند i. تُرجع العقدة التي تحتوي على p أو q نفسها: إذا كانت القيمة الأخرى أسفلها، فهي الإجابة، وإلا فسترى عقدة أعلى منهما كليهما. تسأل أي عقدة أخرى كلا الابنين. إذا أرجع كلاهما شيئًا، فهذا يعني أن p وq يقعان على جانبين مختلفين، وهذه العقدة هي موضع التقائهما؛ وإذا أرجع أحدهما شيئًا، فمرّر ذلك إلى الأعلى.
بالنسبة إلى 3 و15، تحصل 8 على الفهرس 3 من ابنها الأيسر والفهرس 10 من ابنها الأيمن، ثم تُرجع نفسها. قد تزور كل عقدة: زمن 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)]قارن بين مساري البحث
الفكرة
ابحث عن قيمة بالطريقة المعتادة: ابدأ من الجذر، واتجه يسارًا عندما تكون القيمة أصغر من العقدة ويمينًا عندما تكون أكبر منها. المسار من الجذر إلى العقدة فريد، لذا يمرّ البحث بكل أسلاف القيمة ولا يمرّ بغيرهم.
سجّل المسارين. فهما يشتركان في العقد حتى تتجه القيمتان في اتجاهين مختلفين، لذا تسرد البداية المشتركة الأسلاف المشتركين، وتكون آخر قيمة فيها هي الأدنى. بالنسبة إلى 3 و15، المساران هما 20, 8, 3 و20, 8, 12, 15: وهما يشتركان في 20, 8، لذا الإجابة هي 8. تستغرق كل عملية بحث خطوة واحدة لكل مستوى: زمن O(h)، ومساحة 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 أعمق عقدة تقع فوق القيمتين. في المثال الثالث، تقع 50 أسفل القيمتين، لذا انتقل إلى اليمين وصولًا إلى 70، حيث تكون 55 أصغر و80 أكبر. يمنحك زوج واحد من المقارنات لكل مستوى زمنًا قدره 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، تتجاوز المسيرة12إلى10، ثم تعيد10أو تخرج من الشجرة. - افتراض أن
p < q. في المثال الثاني، تكون قيمةpأكبر. اختبر كليهما مقابل العقدة، أو بدّل بينهما أولًا. - إرجاع الفهرس بدلًا من القيمة. الإجابة هي
tree[i]، وليستi. - في Lua وR، تبدأ المصفوفات من 1. أبقِ فهارس العقد تبدأ من 0 لحساب
2*i+1، واقرأtree[i + 1].
أسئلة شائعة3
ما التعقيد الزمني لإيجاد السلف المشترك الأدنى في شجرة بحث ثنائية (BST)؟
يسلك المسار بدءًا من الجذر طريقًا واحدًا، لذا يستغرق زمنًا قدره O(h) لشجرة عمقها h، ويستخدم مساحة إضافية قدرها O(1). في شجرة متوازنة، يكون ذلك O(log n)؛ أما في شجرة على شكل مسار واحد، فيكون O(n).
كيف تختلف السلف المشترك الأدنى (LCA) في شجرة بحث ثنائية عن السلف المشترك الأدنى في شجرة ثنائية؟
في شجرة ثنائية عادية، يمكن أن توجد القيمة في أي مكان، لذا قد تبحث في كل عقدة، وهذا يتطلب عملاً بمقدار O(n). أما في شجرة البحث، فإن مقارنة القيمتين بقيمة عقدة تخبرك بأي جهة توجد كل منهما، لذا تتبع مسارًا واحدًا من الجذر.
هل يمكن أن تكون العقدة هي نفسها السلف المشترك الأدنى لها؟
نعم. تُعَدّ العقدة سلفًا لنفسها، لذا عندما تكون p أعلى من q تكون الإجابة هي p، وعندما تتساوى القيمتان تكون الإجابة هي تلك القيمة.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
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