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 عقد.
+13 اختبارات مخفية عند الإرسال
سؤال إضافي
كيف ستُعيد القيم الموجودة في أطول مسار من الجذر إلى الورقة، بدلًا من إرجاع طوله فقط؟ إذا تعادل طول عدة مسارات، فأيّها ستُعيد، وكيف ستوضّح ذلك في العقد؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
فكّر في الجذر. إذا كنت تعرف عمق الشجرة الفرعية اليسرى وعمق الشجرة الفرعية اليمنى، فما عمق الشجرة بأكملها؟
تساوي
1مضافًا إليه العمق الأكبر للفرعين، ويكون عمق الموضع الفارغ0. تنطبق القاعدة نفسها على كل عقدة، لذا يمكن لاجتياز يعرف عمق كل عقدة أن يجد الإجابة.احتفظ بمكدس من الأزواج، يتكون كل منها من فهرس عقدة وعمقها، بدءًا من الجذر عند العمق 1. أخرج زوجًا، وسجّل أكبر عمق تمت رؤيته، وأضف كل ابن عند
2*i+1و2*i+2إذا كان ضمن حدود المصفوفة ولا يساوي-1، مع زيادة العمق بمقدار واحد.
الحل
يُحدَّد العمق بأطول فرع، ولا يمكنك معرفة أيّ الفروع هو الأطول من دون النظر إلى كل عقدة. لذا تتطلب المهمة اجتيازًا كاملًا يتتبّع العمق عند كل عقدة. تُنجز ذلك في مرور واحد كلٌّ من الاستدعاء الذاتي، والبحث بالعرض مستوىً تلو الآخر، والبحث بالعمق باستخدام مكدس خاص بك؛ والاختلاف بينها هو طريقة تتبّعها لموضعك.
الاستدعاء الذاتي على الشجرتين الفرعيتين
الفكرة
أولًا، كيفية التنقّل في المصفوفة. للعقدة عند الفهرس i ابن أيسر عند 2*i+1 وابن أيمن عند 2*i+2. لا يكون الابن موجودًا إلا إذا كان فهرسه ضمن حدود المصفوفة وكانت القيمة عنده ليست -1. في [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]، للعقدة الجذرية 5 ابنان عند الفهرسين 1 و2، وللعقدة 8 عند الفهرس 1 موضع أيسر فارغ عند 3، والعقدة 3 عند الفهرس 4 على يمينها، وتوجد العقدة 6 أسفل تلك العقدة 3 عند الفهرس 9.
والآن الفكرة. يمتد أعمق مسار يمر عبر عقدة نزولًا إلى أيٍّ من فرعيها كان أعمق. لذا فإن عمق الشجرة الفرعية عند الفهرس i يساوي 1 للعقدة نفسها مضافًا إليه الأكبر من العمقين عند 2*i+1 و2*i+2. يبلغ عمق الموضع الفارغ 0، وهذا ما ينهي الاستدعاء التكراري. تحصل الورقة على 1 + max(0, 0) = 1، ثم ترتفع القيم عائدةً إلى الجذر.
تُزار كل عقدة مرة واحدة، لذا يكون الزمن O(n). يحتفظ مكدس الاستدعاءات بإطار واحد لكل مستوى من المسار الحالي، أي O(h) حيث إن h هو العمق، ويبلغ 14 كحد أقصى هنا. هذا الحد هو ما يجعل الاستدعاء التكراري آمنًا في هذه المسألة. أما في شجرة قائمة على المؤشرات وممتدة كسلسلة طويلة، فستتجاوز الشيفرة نفسها حد الاستدعاء التكراري، وهو 1000 إطار في Python.
الخوارزمية
- اكتب
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(n). وتحتوي قائمة الانتظار على مستوى واحد في كل مرة، بمساحة O(w) لأعرض مستوى w. في الشجرة الكاملة، يحتوي المستوى السفلي على نحو نصف عدد العقد، أي 8192 من أصل 16383 عند العمق 14.
الخوارزمية
- ضع فهرس الجذر
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.
أخرج زوجًا من المكدس، وقارن عمقه بأكبر عمق رُصد حتى الآن، ثم أضف كل ابن حقيقي مع depth + 1. تُضاف كل عقدة في الشجرة مرة واحدة فقط، حاملةً طول المسار الذي يصل إليها، لذا فإن أكبر عمق تُخرجه هو الإجابة. في المثال الأول، تُضاف القيمة 6 عند الفهرس 9 على هيئة (9, 4)، ولا يصل أي زوج إلى عمق أكبر.
التعقيد الزمني هو O(n). يحتوي المكدس على الأشقاء الذين ينتظرون المعالجة على طول المسار الحالي، وبحد أقصى يقارب شقيقًا واحدًا لكل مستوى، لذا فإن التعقيد المكاني هو 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
أخطاء شائعة وحالات حدّية
معظم الإجابات الخاطئة عن هذه المسألة تكون بسبب خطأ بمقدار واحد، أو بسبب التعامل مع خانة فارغة على أنها عقدة.
- عدّ الحواف بدلًا من العقد. عمق العقدة الواحدة هو
1هنا؛ لذا فإن إرجاع0لها، أو3لمسار يتكوّن من 4 عقد، ينقصه واحد. - تجاوز التحقق من الحدود. قد تتجاوز فهارس أبناء ورقة قريبة من نهاية المصفوفة آخر مدخل فيها، لأن المصفوفة قد تنتهي مباشرةً بعد العقدة الأخيرة. تحقّق من
child < nقبل قراءةtree[child]. - استنتاج العمق من طول المصفوفة. قد تحتوي المصفوفة على مدخلات إضافية بقيمة
-1في نهايتها، لذا قد يشير طولها إلى مستوى أعمق من أي عقدة فعلية. - التعامل مع
-1على أنه قيمة. فهو يشير إلى عقدة مفقودة، لذا يجب ألّا يُضاف إلى المكدس أو قائمة الانتظار أو يُحتسب. - افتراض أن الشجرة متوازنة. تتحدد الإجابة وفقًا لأطول فرع، كما في سلسلة يسارية تتكوّن من 14 عقدة تكون فيها كل خانة يمنى فارغة.
- قراءة حجم قائمة الانتظار داخل الحلقة في نسخة البحث بعرض الشجرة. يتغير الحجم عند إضافة الأبناء، لذا احفظه قبل بدء الدفعة.
- الخلط بين الإزاحة في Lua وR، حيث تبدأ المصفوفات من 1. أبقِ فهارس العقد بدءًا من 0 لتوافق عملية الحساب
2*i+1، واقرأtree[i + 1].
أسئلة شائعة4
ما هو التعقيد الزمني لإيجاد أقصى عمق لشجرة ثنائية؟
تزور كل طريقة كل عقدة مرة واحدة، لذا يكون الزمن O(n). تستخدم إصدارات البحث بالعمق مساحة إضافية O(h) للمسار الجاري استكشافه، حيث يمثّل h العمق. ويستخدم إصدار البحث بالعرض O(w) لأعرض مستوى، وقد يضم هذا المستوى نحو نصف العقد في شجرة ممتلئة.
هل ينبغي استخدام DFS أم BFS لإيجاد أقصى عمق لشجرة ثنائية؟
كلاهما يعطي الإجابة الصحيحة في زمن O(n). البحث بالعمق أقصر في الكتابة ويستخدم ذاكرة تتناسب مع العمق، مما يجعله مناسبًا للأشجار العريضة والضحلة. أما البحث بالعرض فيعدّ المستويات مباشرةً ويستخدم ذاكرة تتناسب مع أوسع مستوى، مما يجعله مناسبًا للأشجار العميقة والضيقة. ولإيجاد الحد الأدنى للعمق، يتفوق البحث بالعرض، لأنه يستطيع التوقف عند أول ورقة يصادفها.
كيف تجد أقصى عمق لشجرة ثنائية دون استخدام الاستدعاء التعاودي؟
استخدم مكدسًا صريحًا من الأزواج: عقدة وعمقها. ابدأ بالجذر عند العمق 1، واسحب زوجًا، وسجّل عمقه، ثم أضف كل ابن إلى المكدس مع عمق يزيد بمقدار واحد. أكبر عمق تسحبه هو الإجابة. ويمكن أيضًا استخدام طابور تتم معالجته مستوىً تلو الآخر، مع احتساب واحد لكل مستوى.
ما الفرق بين عمق الشجرة الثنائية وارتفاعها؟
يُحسب عمق العقدة بعدد الخطوات من الجذر نزولًا إليها، ويُحسب ارتفاع العقدة بعدد الخطوات منها نزولًا إلى أعمق ورقة فيها. أقصى عمق للشجرة وارتفاع الجذر هما العدد نفسه. تحتسب هذه المسألة العقد، لذا يكون عمق العقدة الوحيدة 1؛ بينما تحتسب بعض الكتب الحواف بدلًا من ذلك، ما يعطي عددًا أقل بواحد.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def maxDepth(tree):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
المتوقع
4