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: true אם סכום הערכים במסלול מהשורש לעלה שווה ל־targetSum, אחרת false

אילוצים

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 לעיתים קרובות מדי, למשל כשהערך של השורש לבדו שווה ליעד, אבל יש לשורש ילד. צומת מסיים מסלול רק כששני המקומות של ילדיו ריקים.

האם אפשר לפתור את Path Sum באמצעות BFS?

כן. שים זוגות של צומת וסכום המסלול שלו בתור במקום במחסנית, ובדוק כל עלה כשהוא יוצא. זמן הריצה עדיין O(n), אבל התור יכול להכיל רמה שלמה, בערך חצי מהצמתים של עץ מלא, בעוד שמחסנית מכילה בערך צומת אחד לכל רמה.

איך מוצאים כל מסלול שסכומו שווה ליעד?

שמרו את רשימת הצמתים שבמסלול הנוכחי בזמן הירידה, העתיקו אותה לתשובה בכל עלה שסכומו תואם, והסירו את הצומת האחרון כשעולים בחזרה. הסריקה נשארת זהה; רק ניהול המידע גדל. העתקת המסלולים עשויה לעלות יותר מהסריקה עצמה כשצמתים רבים תואמים.

Python

def hasPathSum(tree, targetSum):
    # כתבו כאן את הקוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

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

צפוי

true