Maximum Depth 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 = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
- المخرجات
- 4
- الشرح
- أطول مسار هو
5،8،3،6(الفهارس0،1،4،9)، ويتكوّن من 4 عقد. يتوقف المسار الذي يمر عبر1بعد عقدتين.
- المدخلات
- tree = [7, -1, -1]
- المخرجات
- 1
- الشرح
- يمثل المدخلان
-1موضعي الابنين الفارغين للجذر. يشكّل الجذر وحده مسارًا من عقدة واحدة، لذا فالعمق هو1وليس0.
- المدخلات
- tree = [2, -1, 9, -1, -1, -1, 4]
- المخرجات
- 3
- الشرح
- الجذر
2ليس له ابن أيسر. ابنه الأيمن9عند الفهرس2لديه4عند الفهرس6بوصفه ابنه الأيمن، وهو مسار يتكوّن من 3 عقد.
سؤال إضافي
كيف ستُرجع القيم الموجودة على أطول مسار من الجذر إلى الورقة، بالإضافة إلى طوله؟ إذا تعادلت عدة مسارات، فأيّها ستُرجع؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
فكّر في الجذر. إذا كنت تعرف عمق الشجرة الفرعية اليسرى وعمق الشجرة الفرعية اليمنى، فما عمق الشجرة بأكملها؟
إنها
1للجذر زائد العمق الأكبر للشجرتين الفرعيتين، ويكون عمق الموضع الفارغ0. تنطبق القاعدة نفسها على كل عقدة، لذا يمكن لاجتياز يعرف عمق كل عقدة أن يجد الإجابة.احتفظ بمكدس من الأزواج، يتكوّن كل منها من فهرس عقدة وعمقها، وابدأ من الجذر عند العمق 1. أخرج زوجًا من المكدس، وتذكّر أكبر عمق تمت رؤيته، وأضف كل ابن عند
2*i+1و2*i+2إذا كان ضمن حدود المصفوفة ولا يساوي-1، مع زيادة العمق بمقدار واحد.
الحل
يُحدَّد العمق بأطول فرع، ولا يمكنك معرفة أيّ الفروع هو الأطول من دون زيارة كل عقدة. لذلك تحتاج إلى اجتياز كامل واحد يعرف مدى العمق عند كل عقدة. وتنجز ذلك كلٌّ من العودية، والبحث بالعرض حسب المستويات، والبحث بالعمق باستخدام مكدس خاص بك، في مرور واحد.
الاستدعاء الذاتي على الشجرتين الفرعيتين
الفكرة
يكون الموضع الابن حقيقيًا عندما يكون فهرسه داخل المصفوفة وتكون قيمته ليست -1. يمتد المسار الأعمق عبر العقدة إلى أسفل داخل شجرتها الفرعية الأعمق، لذا يكون العمق عند الفهرس i هو 1 للعقدة مضافًا إليه الأكبر من العمقين عند 2*i+1 و2*i+2. عمق الموضع الفارغ هو 0، وهذا ينهي الاستدعاء التكراري. تحصل الورقة على 1 + max(0, 0) = 1، ثم ترتفع القيم عائدةً إلى الجذر.
تُزار كل عقدة مرة واحدة. يحتفظ مكدس الاستدعاءات بإطار واحد لكل مستوى من المسار الحالي، O(h)، وبحد أقصى 14 هنا.
الخوارزمية
- اكتب
depth(i): إذا تجاوزiنهاية المصفوفة أو كانتtree[i]تساوي-1، فأعِد0. - وإلا فأعِد
1 + max(depth(2*i+1), depth(2*i+2)). - أعِد
depth(0).
def maxDepth(tree):
def depth(i):
# An index past the end or a -1 is an empty spot: depth 0.
if i >= len(tree) or tree[i] == -1:
return 0
return 1 + max(depth(2 * i + 1), depth(2 * i + 2))
return depth(0)البحث بعرض المستوى، مستوى تلو الآخر
الفكرة
الحد الأقصى للعمق هو عدد المستويات، لذا يمكنك عدّ المستويات بدلًا من تتبّع المسارات. تزور قائمة الانتظار العقد بترتيب المستويات. قبل كل دفعة، اقرأ حجم قائمة الانتظار: فهذه العقد تشكّل مستوى واحدًا بالضبط، لأن الأبناء الذين تضيفهم أثناء الدفعة يُضافون إلى ما بعدها. تضيف كل دفعة 1 إلى العمق. في المثال الأول، الدفعات هي [5] و[8, 1] و[3] و[6]، لذا الإجابة هي 4.
تحتفظ قائمة الانتظار بمستوى واحد في كل مرة، O(w) لأعرض مستوى. في شجرة كاملة عمقها 14، يكون ذلك 8192 من أصل 16383 عقدة.
الخوارزمية
- ضع فهرس الجذر
0في قائمة انتظار واضبطdepth = 0. - ما دامت قائمة الانتظار غير فارغة، أضف
1إلىdepthواقرأ حجم قائمة الانتظار. - أخرج هذا العدد من الفهارس. ولكل منها، أضف فهرسي الابنين
2*i+1و2*i+2إلى قائمة الانتظار إذا كانا داخل المصفوفة ولا يساويان-1. - عندما تصبح قائمة الانتظار فارغة، أعد
depth.
from collections import deque
def maxDepth(tree):
n = len(tree)
queue = deque([0])
depth = 0
while queue:
depth += 1
for _ in range(len(queue)): # exactly the nodes of this level
i = queue.popleft()
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
queue.append(child)
return depthالبحث بالعمق باستخدام مكدس صريح
الفكرة
احتفظ بمكدس خاص بك من الأزواج، يتضمن فهرس العقدة وعمقها، إذ لا شيء آخر يتذكر مدى عمق العقدة. ابدأ بـ (0, 1)، الجذر عند العمق 1. تُضاف كل عقدة إلى المكدس مرة واحدة، حاملةً طول المسار الذي يصل إليها، لذا فإن أكبر عمق تسحبه من المكدس هو الإجابة. في المثال الأول، تُضاف 6 إلى المكدس على هيئة (9, 4).
يحتوي المكدس على نحو شقيق واحد معلّق لكل مستوى، O(h)، من دون مكدس استدعاءات قد يفيض. تعمل الشيفرة نفسها على شجرة قائمة على المؤشرات بأي عمق.
الخوارزمية
- أضِف
(0, 1)إلى المكدس واجعلbest = 0. - أزِل زوجًا
(i, depth)من المكدس واجعلbestمساويًا للأكبر بينbestوdepth. - لكل فهرس ابن
2*i+1و2*i+2يقع ضمن حدود المصفوفة ولا يساوي-1، أضِفه إلى المكدس معdepth + 1. - كرّر حتى يصبح المكدس فارغًا، ثم أعد
best.
def maxDepth(tree):
n = len(tree)
best = 0
stack = [(0, 1)] # (node index, depth of that node); the root is never empty
while stack:
i, depth = stack.pop()
best = max(best, depth)
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
stack.append((child, depth + 1))
return best
أخطاء شائعة وحالات حدّية
- عدّ الحواف بدلًا من العقد.
[7, -1, -1]له عمق1، وليس0. - تخطّي التحقق من الحدود. في المثال الأول، للعقدة
6عند الفهرس 9 فهرسا ابنين هما 19 و20، وهما خارج نهاية المصفوفة. تحقّق منchild < nقبل قراءةtree[child]. - حساب العمق من طول المصفوفة. تصل عناصر
-1اللاحقة إلى مستوى لا توجد فيه عقدة: طول[7, -1, -1]هو 3، لكن عمقه 1. - قراءة حجم قائمة الانتظار داخل حلقة الدفعة. تتغير قيمته عند إضافة أبناء أثناء الدفعة، لذا احفظه أولًا.
- الخلط بين الإزاحة في Lua وR، حيث تبدأ المصفوفات من 1. أبقِ فهارس العقد بدءًا من 0 عند استخدام
2*i+1، واقرأtree[i + 1].
أسئلة شائعة3
ما هو التعقيد الزمني لإيجاد أقصى عمق لشجرة ثنائية؟
يزور كل نهج كل عقدة مرة واحدة، لذا فإن الزمن هو O(n). تستخدم إصدارات البحث بالعمق أولًا مساحة إضافية قدرها O(h) للمسار الحالي، حيث h هو العمق. ويستخدم إصدار البحث بالعرض أولًا O(w) لأعرض مستوى، أي نحو نصف العقد في شجرة كاملة.
هل ينبغي استخدام DFS أم BFS لإيجاد أقصى عمق لشجرة ثنائية؟
كلاهما يعمل بزمن O(n). كتابة البحث بالعمق أولًا أقصر، ويستخدم ذاكرة تتناسب مع العمق، ما يجعله مناسبًا للأشجار العريضة والضحلة. ويحسب البحث بالعرض أولًا المستويات مباشرةً، ويستخدم ذاكرة تتناسب مع أعرض مستوى، ما يجعله مناسبًا للأشجار العميقة والضيقة. ولإيجاد الحد الأدنى للعمق، يتفوق البحث بالعرض أولًا لأنه يستطيع التوقف عند أول ورقة.
ما الفرق بين عمق الشجرة الثنائية وارتفاعها؟
يُحسب عمق العقدة بعدد الخطوات من الجذر نزولًا إليها؛ ويُحسب الارتفاع بعدد الخطوات منها نزولًا إلى أعمق ورقة فيها. يساوي أقصى عمق للشجرة ارتفاع الجذر. تحتسب هذه المسألة العقد، لذا يكون عمق العقدة الوحيدة 1؛ أما احتساب الحواف فيعطي قيمة أقل بواحد.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def maxDepth(tree):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
وسيط
tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
الإخراج المتوقع
4