Path Sum

Q: ما هو التعقيد الزمني لمسألة مجموع المسار؟

تتم زيارة كل عقدة مرة واحدة على الأكثر، لذا يكون الزمن O(n) ، ويمكن إيقاف البحث عند أول ورقة مطابقة. المساحة الإضافية هي O(h) للمسار الجاري استكشافه، سواء أكان ذلك على هيئة إطارات استدعاء أم عناصر في مكدسك الخاص.

سهلاجتياز الأشجار

+10

لديك شجرة ثنائية مخزّنة في المصفوفة tree بترتيب المستويات، ورقم targetSum. يقع الجذر عند الفهرس 0، ويقع ابنا العقدة عند الفهرس i عند 2*i+1 (الأيسر) و2*i+2 (الأيمن)، وتشير -1 إلى موضع فارغ، وقد تنتهي المصفوفة بعناصر -1 إضافية. أعد true إذا كان هناك مسار من الجذر نزولًا إلى ورقة تكون مجموع قيمه مساويًا لـ targetSum، وأعد false خلاف ذلك. الورقة هي عقدة ليس لها أبناء: كلا موضعي ابنيها فارغان.

الدالة

hasPathSum(tree: integer-array, targetSum: integer) → boolean

treeinteger-array: الشجرة الثنائية بترتيب المستويات، مع استخدام -1 للدلالة على موضع فارغ
targetSuminteger: المجموع الذي يجب أن يصل إليه المسار من الجذر إلى الورقة
تُرجعboolean: صحيح إذا كان مجموع إحدى المسارات من الجذر إلى الورقة يساوي targetSum، وخطأ في غير ذلك

القيود

1 ≤ tree.length ≤ 32767
كل عنصر من tree[i] إما -1 أو قيمة تحقق 0 ≤ tree[i] ≤ 1000.
tree[0] لا تكون أبدًا -1، لذا تحتوي الشجرة على عقدة واحدة على الأقل.
قد تنتهي المصفوفة بعناصر -1 إضافية بعد آخر عقدة.
ابنا الموضع الفارغ فارغان أيضًا، والعمق لا يتجاوز 14.
0 ≤ targetSum ≤ 15000

أمثلة

المدخلات: tree = [3, 9, 6, -1, 2, 1, 7]targetSum = 14
المخرجات: true
الشرح: المسار 3، 9، 2 (الفهارس 0، 1، 4) مجموعه 14، و2 عند الفهرس 4 ورقة.

المدخلات: tree = [3, 9, 6, -1, 2, 1, 7]targetSum = 12
المخرجات: false
الشرح: 3 + 9 = 12، لكن 9 لها ابن، لذا لا ينتهي أي مسار عندها. مجموع المسارات الثلاثة من الجذر إلى الورقة هو 14 و10 و16، ولا يساوي أيٌّ منها 12.

المدخلات: tree = [4, -1, -1]targetSum = 4
المخرجات: true
الشرح: موضعا الابنين في الجذر فارغان، لذا فالجذر ورقة بمفرده. مجموع المسار الذي يحتوي على 4 فقط هو 4.

+14 اختبارات مخفية عند الإرسال

سؤال إضافي

هل يمكنك عدّ المسارات التي يكون مجموعها targetSum، عندما يُسمح للمسار أن يبدأ عند أي عقدة وينتهي عند أي عقدة أسفلها، وليس فقط أن يمتد من الجذر إلى ورقة؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

السؤال يتعلق بالمسارات الكاملة، من الجذر حتى الورقة. قد يصل المجموع الجاري إلى targetSum في منتصف المسار إلى الأسفل، عند عقدة لا يزال لها أبناء، وهذا لا يُحتسب. لذا، احمل مجموع المسار حتى الآن إلى كل عقدة، وقارنه بالهدف عند الأوراق فقط. يحمل الاستدعاء الذاتي هذا المجموع كمعامل؛ ويحمله المكدس بجوار كل عقدة.

الاستدعاء الذاتي على المجموع المتبقي

الفكرة

أولًا، كيفية التنقّل داخل المصفوفة. العقدة عند الفهرس i لها ابن أيسر عند 2*i+1 وابن أيمن عند 2*i+2. لا يكون الابن موجودًا فعليًا إلا إذا كان فهرسه داخل المصفوفة وكانت القيمة هناك ليست -1. في [3, 9, 6, -1, 2, 1, 7]، للجذر 3 ابنان عند الفهرسين 1 و2، وللعقدة 9 عند الفهرس 1 موضع أيسر فارغ عند 3، والابن 2 عند الفهرس 4 على يمينها.

والآن الفكرة. يبدأ المسار الذي يكون مجموع قيمه targetSum بقيمة الجذر، لذا يجب أن يكون مجموع بقية المسار، الذي يبدأ عند أحد ابني الجذر، مساويًا لـ targetSum مطروحًا منه تلك القيمة. وهذا هو السؤال نفسه على شجرة أصغر. اطرح قيمة كل عقدة أثناء النزول. عند الورقة ينتهي المسار، لذا تكون الإجابة هناك هي ما إذا لم يتبقَّ شيء.

في المثال الأول، يتبقى بعد الجذر 14 - 3 = 11، وبعد العقدة 9 يتبقى 2، وبعد الورقة 2 يتبقى 0: true. في المثال الثاني، يتبقى بعد العقدة 9 بالفعل 0، لكنها تملك ابنًا، لذا يستمر البحث، وتنتهي ورقتها عند -2. تُزار كل عقدة مرة واحدة على الأكثر، بزمن O(n)، ويحفظ مكدس الاستدعاءات إطارًا واحدًا لكل مستوى، أي O(h)، وبحد أقصى 15 إطارًا هنا (فالعمق 14 يحسب الحواف أسفل الجذر).

الخوارزمية

اكتب walk(i, remaining) واطرح tree[i] من remaining.
إذا كان موضعا الابنين لـ i فارغين (الفهرس يتجاوز النهاية أو -1)، فأعِد ما إذا كانت قيمة remaining تساوي 0.
وإلا فأعِد true إذا أعاد استدعاء walk على ابن أيسر موجود أو ابن أيمن موجود true.
أعِد walk(0, targetSum).

def hasPathSum(tree, targetSum):
    n = len(tree)

    def walk(i, remaining):
        # remaining is what the path still needs once it reaches node i.
        remaining -= tree[i]
        left, right = 2 * i + 1, 2 * i + 2
        has_left = left < n and tree[left] != -1
        has_right = right < n and tree[right] != -1
        if not has_left and not has_right:
            return remaining == 0  # a leaf: the path ends here
        return (has_left and walk(left, remaining)) or (has_right and walk(right, remaining))

    return walk(0, targetSum)

البحث بالعمق باستخدام مكدس صريح

الفكرة

يحتفظ الاستدعاء التكراري بعدد واحد في كل استدعاء: المقدار المتبقي من الهدف. يمكنك الاحتفاظ بهذا العدد بنفسك، على مكدس بجانب كل عقدة، والاستغناء عن الاستدعاءات. خزّن مجموع المسار من الجذر نزولًا إلى العقدة، شاملًا العقدة نفسها. ابدأ بـ (0, tree[0])، وأعطِ كل ابن مجموعَ أبيه مضافًا إليه قيمته.

أخرج زوجًا من المكدس. إذا كانت العقدة ورقة وكان مجموعها يساوي targetSum، فقد انتهيت. وإلا فأضف أبناءها الفعليين إلى المكدس. في المثال الأول، يُسحب الجانب الأيمن من المكدس أولًا: تحمل الورقتان 7 و1 المجموعين 16 و10. ثم يُسحب (1, 12) الخاص بالعقدة 9. وهي ليست ورقة، لذا تضيف (4, 14)، وهي ورقة ذات المجموع المطلوب.

تُضاف كل عقدة فعلية إلى المكدس مرة واحدة، لذا يكون الزمن O(n)، ويتوقف البحث عند أول ورقة مطابقة. يحتوي المكدس على الأشقاء المنتظرين على طول المسار الحالي، واحدًا تقريبًا لكل مستوى، وتكون المساحة O(h). تعمل الحلقة نفسها على شجرة عميقة قائمة على المؤشرات، حيث قد ينفد المكدس مع الاستدعاء التكراري.

الخوارزمية

أضف (0, tree[0]) إلى المكدس.
أخرج زوجًا (i, total) وانظر إلى موضعي الابنين 2*i+1 و2*i+2.
إذا لم يكن أيٌّ من الابنين حقيقيًا وكان total يساوي targetSum، فأعِد true.
أضف كل ابن حقيقي c على هيئة (c, total + tree[c]).
عندما يصبح المكدس فارغًا، أعِد false.

def hasPathSum(tree, targetSum):
    n = len(tree)
    stack = [(0, tree[0])]  # (node index, sum of the path from the root to it)
    while stack:
        i, total = stack.pop()
        left, right = 2 * i + 1, 2 * i + 2
        has_left = left < n and tree[left] != -1
        has_right = right < n and tree[right] != -1
        if not has_left and not has_right and total == targetSum:
            return True  # a leaf whose path adds up
        if has_left:
            stack.append((left, total + tree[left]))
        if has_right:
            stack.append((right, total + tree[right]))
    return False

أخطاء شائعة وحالات حدّية

يتعلّق كل خطأ تقريبًا في هذه المسألة بالمكان الذي ينتهي عنده المسار.

مقارنة المجموع عند كل عقدة. في المثال الثاني، تتطابق 3 + 9 = 12 عند 9، وهي عقدة لها ابن، لذا تكون الإجابة false. قارن عند الأوراق فقط.
اعتبار الموضع الفارغ للابن نهايةً للمسار. إذا أعادت walk عند موضع فارغ القيمة remaining == 0، فستُحتسب 9 في المثال الثاني ورقةً عبر موضع ابنها الأيسر الفارغ. لا تكون العقدة ورقةً إلا عندما يكون الموضعان فارغين.
نسيان الجذر وحده. العقدة الوحيدة ورقة، لذا فإن [4] مع targetSum = 4 تساوي true، وكذلك [0] مع targetSum = 0.
إيقاف البحث بمجرد أن يتجاوز المجموع الهدف. القيم هنا ليست سالبة أبدًا، لذا فهذا آمن في هذه المسألة، لكن الشيفرة نفسها تعطي إجابات خاطئة بمجرد أن تتمكن الشجرة من احتواء قيم سالبة.
القراءة بعد نهاية المصفوفة. قد تكون فهارس أبناء الورقة القريبة من نهاية المصفوفة أكبر من فهرس آخر عنصر فيها، لأن المصفوفة قد تنتهي مباشرةً بعد العقدة الأخيرة. تحقّق من الفهرس قبل قراءة tree[c].
الخلط في الإزاحة في Lua وR، حيث تبدأ المصفوفات من 1. أبقِ فهارس العقد تبدأ من 0 لحساب 2*i+1، واقرأ tree[i + 1].

أسئلة شائعة4

ما هو التعقيد الزمني لمسألة مجموع المسار؟

تتم زيارة كل عقدة مرة واحدة على الأكثر، لذا يكون الزمن O(n)، ويمكن إيقاف البحث عند أول ورقة مطابقة. المساحة الإضافية هي O(h) للمسار الجاري استكشافه، سواء أكان ذلك على هيئة إطارات استدعاء أم عناصر في مكدسك الخاص.

لماذا يتحقق Path Sum من المجموع عند العقد الورقية فقط؟

تطلب المسألة إيجاد مسار من الجذر إلى ورقة، والمسار الذي ينتهي عند عقدة لها أبناء لا يُعدّ كذلك. إن التحقق عند كل عقدة يُرجع true أكثر مما ينبغي، مثلًا عندما تساوي قيمة الجذر وحدها الهدف، مع أن للجذر ابنًا. لا تنتهي العقدة مسارًا إلا عندما يكون موضعا ابنيها فارغين.

هل يمكن حل مسألة مجموع المسار باستخدام البحث بالعرض أولًا؟

نعم. ضع أزواجًا تتكوّن من عقدة ومجموع المسار الخاص بها في طابور بدلًا من مكدّس، وافحص كل ورقة عند إخراجها. يظل الزمن O(n)، لكن الطابور قد يحتوي على مستوى كامل، أي نحو نصف عقد الشجرة الممتلئة، بينما يحتوي المكدّس على نحو عقدة واحدة لكل مستوى.

كيف تجد كل مسار يكون مجموع عناصره مساويًا للهدف؟

احتفِظ بقائمة العقد الموجودة في المسار الحالي أثناء النزول، وانسخها إلى الإجابة عند كل ورقة يطابق مجموعها المطلوب، وأزِل العقدة الأخيرة عند الرجوع إلى الأعلى. يظل الاجتياز كما هو؛ إنما تزداد أعمال حفظ الحالة. قد يستغرق نسخ المسارات وقتًا أطول من الاجتياز نفسه عندما تطابق أوراق كثيرة.

Python

def hasPathSum(tree, targetSum):
    # اكتب الكود هنا

حالات الاختبار

الحالة 1

الحالة 2

الحالة 3

المدخلات

tree = [3, 9, 6, -1, 2, 1, 7]
targetSum = 14

المتوقع

true