Diameter of Binary Tree
لديك شجرة ثنائية مخزّنة في المصفوفة tree بترتيب المستويات. يقع الجذر عند الفهرس 0، ويقع ابنا العقدة عند الفهرس i عند 2*i+1 (الأيسر) و2*i+2 (الأيمن)، ويشير -1 إلى موضع فارغ، وقد تنتهي المصفوفة بعناصر -1 إضافية. أعد قطر الشجرة: عدد الحواف في أطول مسار بين أي عقدتين. قد يمر المسار عبر الجذر أو يبقى داخل شجرة فرعية واحدة.
الدالة
- treeinteger-array
- الشجرة الثنائية بترتيب المستويات، مع استخدام -1 للدلالة على موضع فارغ
- تُرجعinteger
- عدد الحواف في أطول مسار بين عقدتين
القيود
1 ≤ tree.length ≤ 32767- كل عنصر
tree[i]إما-1أو قيمة تحقق0 ≤ tree[i] ≤ 1000. - لا تكون
tree[0]أبدًا-1، لذا تحتوي الشجرة على عقدة واحدة على الأقل. - قد تنتهي المصفوفة بعناصر
-1إضافية بعد آخر عقدة. - كلا الفرعين من الموضع الفارغ فارغان أيضًا، والعمق لا يزيد عن
14.
أمثلة
- المدخلات
- tree = [8, 3, 6, 1, 4, -1, -1, -1, -1, 7]
- المخرجات
- 4
- الشرح
- يحتوي المسار
7،4،3،8،6(الفهارس9،4،1،0،2) على خمس عقد متصلة بأربع حواف. وينعطف عند الجذر: ثلاث حواف نزولًا على الجانب الأيسر وواحدة نزولًا على الجانب الأيمن.
- المدخلات
- tree = [2, 5, -1, 1, 9, -1, -1, 3, -1, -1, 4]
- المخرجات
- 4
- الشرح
- المسار
3،1،5،9،4يتكوّن من أربع حواف، وينعطف عند5في الفهرس1. ليس للجذر ابن أيمن، لذا لا يتضمن المسار المار عبر الجذر سوى الحواف الثلاثة الممتدة على جانبه الأيسر.
- المدخلات
- tree = [6, -1, -1]
- المخرجات
- 0
- الشرح
- لا تحتوي العقدة المفردة على أي حواف. أطول مسار هو العقدة وحدها، وطوله
0.
+12 اختبارات مخفية عند الإرسال
سؤال إضافي
كيف يمكنك إرجاع المسار نفسه، وقيم العُقد من أحد طرفَي القطر إلى الطرف الآخر؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
لكل مسار في الشجرة عقدة واحدة هي الأعلى، حيث يتغير اتجاهه من الصعود إلى الهبوط. إذا عرفت تلك العقدة، فما أقصى طول يمكن أن يكون عليه المسار المار بها؟
المسار الذي ينعطف عند العقدة
iينزل إلى الشجرة الفرعية اليسرى ثم إلى الشجرة الفرعية اليمنى. في أفضل الأحوال، يكون طوله ارتفاع الابن الأيسر زائد ارتفاع الابن الأيمن، حيث يُحسب الارتفاع بعدد العقد في أطول مسار نحو الأسفل، ويكون ارتفاع الموضع الفارغ0.احسب الارتفاعات من الأسفل إلى الأعلى في مرور واحد بترتيب ما بعد الترتيب: ارتفاع العقدة هو
1 + max(left, right). أثناء الاحتفاظ بـleftوrightعند عقدة ما، حدّث الإجابة باستخدامleft + right.
الحل
ليس من الضروري أن يمر أطول مسار عبر الجذر، لذا لا يكفي قياس جانبي الجذر. لكل مسار عقدة واحدة هي الأعلى، حيث يتحول اتجاهه من الصعود إلى الهبوط، ويكون أطول مسار ينعطف عند عقدة ما مساويًا لارتفاعها الأيسر مضافًا إليه ارتفاعها الأيمن. تحسب عملية اجتياز واحدة بترتيب ما بعد الترتيب كل ارتفاع من الأسفل إلى الأعلى، وتتحقق من كل نقطة انعطاف في طريقها، في O(n).
قِسْ كل زوج من العُقَد
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
أولًا، كيفية التنقّل في المصفوفة. العقدة عند الفهرس i لها ابن أيسر عند 2*i+1 وابن أيمن عند 2*i+2، لذا يقع والدها عند (i-1)/2، بعد التقريب إلى الأسفل. لا يكون الموضع حقيقيًا إلا إذا كان فهرسه داخل المصفوفة وكانت قيمته ليست -1. في [8, 3, 6, 1, 4, -1, -1, -1, -1, 7]، يكون والد 7 عند الفهرس 9 هو العنصر عند الفهرس 4، ووالد ذلك العنصر 4 هو العنصر عند الفهرس 1.
القطر هو أكبر مسافة بين عقدتين، لذا يمكنك قياس كل زوج. لإيجاد المسافة بين الفهرسين a وb، اصعد نحو الجذر خطوة واحدة في كل مرة حتى يلتقيا، وابدأ دائمًا من الفهرس الأكبر. لا يكون الفهرس الأكبر أبدًا في مستوى أعلى، لذا لا تتجاوز هذه الخطوة نقطة الالتقاء. عدد الخطوات هو عدد الحواف. بالنسبة إلى 9 و2: يصعد 9 إلى 4 ثم إلى 1، ويصعد 2 إلى 0، ويصعد 1 إلى 0. أربع خطوات.
هذا صحيح لكنه بطيء. أكبر اختبار هو شجرة كاملة تتكون من 16383 عقدة، ما ينتج نحو 1.3 × 10^8 زوجًا، ويستغرق كل زوج ما يصل إلى 26 خطوة. مليارات الخطوات للحصول على إجابة واحدة تتجاوز بكثير الحد الزمني.
الخوارزمية
- اجمع فهارس جميع العقد الحقيقية.
- لكل زوج
(a, b)، عيّنedges = 0وكرّر حتىa == b: استبدل الفهرس الأكبر بأبيه وأضف1إلىedges. - احتفظ بأكبر قيمة لـ
edgesتراها وأعِدها.
def diameterOfBinaryTree(tree):
nodes = [i for i, value in enumerate(tree) if value != -1]
best = 0
for x in range(len(nodes)):
for y in range(x + 1, len(nodes)):
a, b = nodes[x], nodes[y]
edges = 0
while a != b:
# A larger index is never higher up, so climb from it.
if a > b:
a = (a - 1) // 2
else:
b = (b - 1) // 2
edges += 1
best = max(best, edges)
return bestقِس كلا الارتفاعين عند كل عقدة
الفكرة
انظر إلى أطول مسار انطلاقًا من أعلى عقدة فيه، وهي العقدة التي يتوقف عندها المسار عن الصعود ويبدأ بالهبوط. ومن هناك، يمتد إلى أبعد نقطة ممكنة نزولًا على الجانب الأيسر، وإلى أبعد نقطة ممكنة نزولًا على الجانب الأيمن. لنعرّف height(c) على أنه عدد العقد في أطول مسار هابط من c، مع اعتبار الموضع الفارغ ذا القيمة 0. عندئذٍ، يكون طول أطول مسار ينعطف عند العقدة i هو height(2*i+1) + height(2*i+2) من الحواف، بمعدل حافة واحدة لكل عقدة من تلك العقد.
لذا جرّب كل عقدة كنقطة انعطاف واحتفظ بالأفضل. في المثال الثاني، ارتفاع العقدة 5 عند الفهرس 1 هو 2 على اليسار (1، 3) و2 على اليمين (9، 4)، ما يشكّل مسارًا من أربع حواف. أما الجذر، فارتفاعه 3 على اليسار و0 على اليمين، ما يعطي ثلاثة فقط.
كل استدعاء لـ height يجتاز شجرة فرعية كاملة، ويُعاد اجتياز العقدة لكل سلف فوقها، لذا يكون مقدار العمل O(n·h). وبما أن h ≤ 14، فهذا سريع بما يكفي هنا، لكن في شجرة مؤشرات على شكل سلسلة، قد يصل h إلى n، وتكون كلفة الفكرة نفسها O(n²). استدعاءات height المتكررة هي الهدر الذي تزيله الطريقة الأخيرة.
الخوارزمية
- اكتب
height(i):0للموضع الفارغ، وإلا1 + max(height(2*i+1), height(2*i+2)). - لكل عقدة فعلية
i، احسبheight(2*i+1) + height(2*i+2). - أعِد أكبر هذه المجاميع.
def diameterOfBinaryTree(tree):
n = len(tree)
def height(i):
# Nodes on the longest downward path from i; an empty spot has 0.
if i >= n or tree[i] == -1:
return 0
return 1 + max(height(2 * i + 1), height(2 * i + 2))
best = 0
for i in range(n):
if tree[i] != -1:
# The longest path that turns at node i goes down both sides.
best = max(best, height(2 * i + 1) + height(2 * i + 2))
return bestمرور واحد بترتيب لاحق على الارتفاعات
الفكرة
يعتمد ارتفاع العقدة فقط على ارتفاعَي طفليها، وهذان هما الرقمان نفسيهما اللذان يحتاجهما فحص نقطة الانعطاف. لذا احسبهما مرة واحدة، من الأسفل إلى الأعلى. تنهي عملية الاجتياز بترتيب ما بعد الترتيب معالجة كلا الطفلين قبل والدهما. عند كل عقدة، يكون لديك عندئذٍ left وright: حدّث الإجابة باستخدام left + right، وأرسل 1 + max(left, right) إلى العقدة الأب.
في المثال الأول، تُرجع الورقة 7 القيمة 1، وتُرجع العقدة 4 التي تعلوها القيمة 2، وتُرجع العقدة 3 القيمة 3، لأن ارتفاع طفلها الآخر 1 هو 1. وتُرجع العقدة 6 القيمة 1. عند الجذر، تكون left + right = 3 + 1 = 4، وهي الإجابة. وأفضل ما تقدمه أي عقدة أخرى هو 3، مع 1 + 2 = 3.
تُزار كل عقدة مرة واحدة، لذا يكون الزمن O(n)، ويبلغ عمق الاستدعاء التكراري عمق الشجرة، O(h)، أي نحو إطار واحد لكل مستوى. تُحفَظ الإجابة في متغير خارج الاستدعاء التكراري، لأن ما تُرجعه عملية الاستدعاء (ارتفاع) ليس ما تريده في النهاية (طول مسار).
الخوارزمية
- عيّن
best = 0واكتبheight(i). إذا كان الموضع فارغًا، فأعِد0. - احسب
left = height(2*i+1)وright = height(2*i+2). - عيّن
bestإلى الأكبر بينbestوleft + right. - أعِد
1 + max(left, right). - استدعِ
height(0)وأعِدbest.
def diameterOfBinaryTree(tree):
n = len(tree)
best = 0
def height(i):
# Returns the height of node i and updates best on the way back up.
nonlocal best
if i >= n or tree[i] == -1:
return 0
left = height(2 * i + 1)
right = height(2 * i + 2)
best = max(best, left + right) # the longest path that turns at node i
return 1 + max(left, right)
height(0)
return best
أخطاء شائعة وحالات حدّية
معظم الإجابات الخاطئة تعدّ الشيء الخطأ أو تقيس عند العقدة الخطأ.
- عدّ العقد بدلًا من الحواف. يحتوي المسار
7،4،3،8،6على خمس عقد وطوله4، وقطر العقدة الواحدة هو0. - القياس عبر الجذر فقط. في المثال الثاني، يتكوّن أفضل مسار يمر عبر الجذر من ثلاث حواف، بينما الإجابة هي أربعة، إذ ينعطف عند الفهرس
1. - إرجاع القطر من الاستدعاء العودي. يحتاج الأب إلى ارتفاعَي طفليه لبناء مسارات أطول؛ لذا يجب حفظ القطر في متغير منفصل.
- الخلط بين اصطلاحَي الارتفاع. عندما تحسب الارتفاعات عدد العقد وتكون قيمة الموضع الفارغ
0، فإنleft + rightيعطي عدد الحواف مباشرةً. أما الارتفاعات التي تحسب عدد الحواف، فتتطلب أن تكون قيمة الموضع الفارغ-1، وأن تُستخدمleft + right + 2. استخدام نصف أحد الاصطلاحين ونصف الآخر يؤدي إلى فرق بمقدار واحد أو اثنين. - القراءة بعد نهاية المصفوفة. قد تتجاوز فهارس أبناء ورقة قرب نهاية المصفوفة آخر عنصر فيها. اعتبر أي فهرس يتجاوز النهاية موضعًا فارغًا.
- الخلط بين الإزاحة في Lua وR، حيث تبدأ المصفوفات عند 1. أبقِ فهارس العقد بدءًا من 0 لحساب
2*i+1، واقرأtree[i + 1].
أسئلة شائعة4
ما هو التعقيد الزمني لقطر الشجرة الثنائية؟
يزور حلّ الترتيب اللاحق كل عقدة مرة واحدة، لذا يعمل في زمن O(n) مع مساحة إضافية O(h) للاستدعاء التكراري، حيث إن h هو الارتفاع. أما حساب الارتفاعات بصورة منفصلة عند كل عقدة فيتطلب O(n·h)، ويصبح O(n²) في شجرة على شكل سلسلة.
هل يمر قطر الشجرة الثنائية دائمًا عبر الجذر؟
لا. قد يقع أطول مسار بالكامل داخل شجرة فرعية واحدة، مثلًا عندما يكون للجذر فرع قصير وشجرة فرعية عميقة وكثيفة من الجهة الأخرى. لهذا السبب تتحقق من left + right عند كل عقدة، وليس عند الجذر فقط.
هل يُحتسب القطر بالعُقد أم بالحواف؟
يُحسب هنا بعدد الحواف، أي الروابط بين العقد المتتالية على المسار، لذا يكون قطر العقدة الواحدة 0، وقطر عقدتين متصلتين 1. تحسب بعض الكتب عدد العقد بدلًا من ذلك، ما يعطي قيمة أكبر بواحد. تحقّق مما يطلبه السؤال قبل أن تضيف 1 أو تطرحها.
كيف تجد قطر شجرة ثنائية دون استخدام الاستدعاء الذاتي؟
زُر العقد بترتيب يأتي فيه كل ابن قبل أبيه. إحدى الطرق: ادفع الجذر إلى مكدس، وأخرج العقد إلى قائمة مع دفع أبنائها، ثم تصفّح تلك القائمة بالعكس. خزّن ارتفاع كل عقدة في مصفوفة، واقرأ ارتفاعَي الابنين عند كل عقدة، وحدّث الإجابة بمجموعهما. يظل الزمن O(n).
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def diameterOfBinaryTree(tree):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
tree = [8, 3, 6, 1, 4, -1, -1, -1, -1, 7]
المتوقع
4