Construct Binary Tree from Preorder and Inorder Traversal

Q: למה צריך גם סריקת תחילית וגם סריקה תוך־סדרית כדי לבנות מחדש עץ בינארי?

קדם־סדר לבדו אינו קובע את המבנה. קדם־הסדר [1, 2] מתאים לעץ שבו 2 הוא הילד השמאלי של 1 וגם לעץ שבו הוא הילד הימני. סדר־תוך מכריע: [2, 1] מציב את 2 משמאל, ו־ [1, 2] מימין. כאשר הערכים שונים, הצמד מתאר עץ יחיד בדיוק.

Q: מהי סיבוכיות הזמן של בניית עץ בינארי מסריקה בסדר תחילי וסריקה בסדר תוכי?

עם מיפוי מערכים למיקומים בסריקת inorder, זמן הריצה הוא O(n) ונדרש מקום נוסף בנפח O(n) . ללא המיפוי, סריקת כל טווח inorder כדי למצוא את השורש שלו עולה O(n·h) , ובמקרה של עץ שצורתו כשל מסלול העלות היא O(n²) .

Q: האם אפשר לשחזר עץ בינארי באמצעות סריקת קדם וסריקת אחר?

לא באופן כללי. סדר קידומת [1, 2] וסדר סיומת [2, 1] מתאימים גם לילד שמאלי וגם לילד ימני, כי אף אחד מהמעברים לא מציב את השורש בין תתי-העצים שלו. הצמד מספיק רק לעץ בינארי מלא, שבו לכל צומת יש אפס ילדים או שני ילדים.

בינוניסריקת עצים גיבוב רקורסיה

+10

מקבלים שני מערכים, preorder ו־inorder, שמציגים את הערכים הייחודיים של אותו עץ בינארי. בסריקה תחילית מבקרים בצומת, אחר כך בתת־העץ השמאלי שלו, ואז בתת־העץ הימני שלו. בסריקה תוכית מבקרים בתת־העץ השמאלי, אחר כך בצומת, ואז בתת־העץ הימני.

בנו מחדש את העץ והחזירו אותו כמערך בסדר רמות: השורש באינדקס 0, הילדים של האינדקס i באינדקסים 2i+1 (שמאלי) ו־2i+2 (ימני), ואת הערך -1 עבור כל מקום ריק. המערך מסתיים בצומת האחרון, ללא -1 בסופו.

פונקציה

buildTree(preorder: integer-array, inorder: integer-array) → integer-array

preorderinteger-array: הערכים בסדר קדם־סדר: צומת, תת־עץ שמאלי, תת־עץ ימני
inorderinteger-array: הערכים לפי סדר inorder: תת-העץ השמאלי, הצומת, תת-העץ הימני
מחזירהinteger-array: העץ לפי סדר הרמות, עם ‎-1‎ עבור מקומות ריקים וללא ‎-1‎ בסוף

אילוצים

1 ≤ preorder.length ≤ 3000
inorder.length == preorder.length
0 ≤ preorder[i] ≤ 10⁴, וכל הערכים שונים זה מזה.
inorder מכיל את אותם הערכים, ושני המערכים מתארים את אותו עץ בינארי.
עומק העץ הוא לכל היותר 14, לכן כל אינדקס בתשובה קטן מ־2¹⁴-1 = 16383.

דוגמאות

קלט: preorder = [7, 3, 0, 9, 4, 6]inorder = [0, 3, 9, 7, 4, 6]
פלט: [7, 3, 4, 0, 9, -1, 6]
הסבר: מעבר preorder מתחיל בשורש, 7. הוא נמצא במיקום 3 בסדר inorder, ולכן 0, 3, 9 הולכים שמאלה ו-4, 6 הולכים ימינה. ל-4 יש רק ילד ימני, 6, ולכן האינדקס 5 נשאר -1.

קלט: preorder = [1, 2, 3]inorder = [2, 3, 1]
פלט: [1, 2, -1, -1, 3]
הסבר: השורש 1 מופיע אחרון ב־inorder, לכן באינדקס 2 מופיע -1. מבין 2, 3, סדר קדם־המעבר מציג את 2 ראשון, ובסדר האמצעי 3 מופיע אחריו, לכן 3 הוא הילד הימני שלו, באינדקס 4.

שאלת המשך

האם תוכלו לבנות מחדש את העץ ללא רקורסיה, במעבר אחד על preorder באמצעות מחסנית מפורשת?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

סריקת preorder נותנת את השורש של כל תת־עץ: הערך הראשון ברצף שלו. סריקת inorder נותנת את נקודת הפיצול: הערכים שלפני השורש עוברים שמאלה, והערכים שאחריו עוברים ימינה. הפעלה רקורסיבית על שני החצאים בונה מחדש את העץ, ומיפוי מערכים למיקומים שלהם בסריקת inorder מאפשר לאתר כל שורש בצעד אחד.

פיצול רקורסיבי תוך סריקה לאיתור השורש

האינטואיציה

בסריקה תחילית, תת-העץ השמאלי מופיע אחרי השורש שלו ותופס ערך אחד לכל ערך, כלומר m-lo ערכים, כאשר m הוא המיקום של השורש בסריקה האמצעית. תת-העץ הימני מופיע אחריו, ולכן השורש שלו נמצא ב-pre+1+(m-lo). בדוגמה הראשונה, החלק השמאלי 0, 3, 9 מכיל שלושה ערכים, ולכן תת-העץ הימני מתחיל באינדקס 4 בסריקה התחילית, בערך 4.

עומק של לכל היותר 14 מבטיח שכל אינדקס בפלט יהיה קטן מ-2^14-1. מלאו כל כך הרבה תאים ב--1, כתבו כל ערך באינדקס שלו, ובסוף הסירו את ערכי -1 שבסוף.

סריקת כל טווח בסריקה האמצעית כדי למצוא את השורש עולה O(n·h): הטווחים באותה רמה אינם חופפים, ולכן בכל רמה נסרקים לכל היותר n ערכים, כלומר לכל היותר 14 × 3000 = 42000 צעדים כאן. ללא הגבלת עומק, עץ בצורת מסלול הופך את הסיבוכיות ל-O(n²).

אלגוריתם

צרו את out עם 2^14-1 איברים, כולם -1.
כתבו את build(pre, lo, hi, h): אם lo > hi, החזירו. אחרת, כתבו את preorder[pre] אל out[h].
סרקו את inorder מ־lo כדי למצוא את המיקום m של השורש. בתת־העץ השמאלי יש m-lo ערכים.
קראו ל־build(pre+1, lo, m-1, 2*h+1) ול־build(pre+1+(m-lo), m+1, hi, 2*h+2).
קראו ל־build(0, 0, n-1, 0), לאחר מכן הסירו את איברי ה־-1 שבסוף והחזירו את השאר.

def buildTree(preorder, inorder):
    out = [-1] * (2 ** 14 - 1)  # every index of a depth-14 tree is below 2^14-1

    def build(pre, lo, hi, h):
        # preorder[pre] is the root of the subtree that inorder[lo..hi] lists;
        # it goes to index h of the output.
        if lo > hi:
            return
        value = preorder[pre]
        out[h] = value
        m = lo
        while inorder[m] != value:  # find the root in the inorder range
            m += 1
        left_size = m - lo
        build(pre + 1, lo, m - 1, 2 * h + 1)
        build(pre + 1 + left_size, m + 1, hi, 2 * h + 2)

    build(0, 0, len(inorder) - 1, 0)
    last = len(out) - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

פיצול רקורסיבי עם מפת מיקומים

האינטואיציה

הערכים שונים זה מזה, ולכן לכל אחד מהם יש מיקום יחיד ב־inorder. תעדו אותו במפה מערך למיקום לפני תחילת הרקורסיה, וכך כל חיפוש של שורש ידרוש צעד אחד.

בניית המפה אורכת O(n), ואז כל ערך ממוקם פעם אחת בעבודה בזמן קבוע, ולכן זמן הריצה הכולל הוא O(n). המפה צורכת O(n) מקום, והרקורסיה צורכת מסגרת אחת לכל רמה. ב־C וב־R הערכים הם לכל היותר 10^4, ולכן מערך רגיל עם 10^4+1 איברים משמש כמפה.

אלגוריתם

בנה מפה מכל ערך של inorder למיקום שלו.
צור את out עם 2^14-1 איברים, כולם -1.
ב־build(pre, lo, hi, h), החזר אם lo > hi; אחרת כתוב את preorder[pre] לתוך out[h] וחפש במפה את המיקום שלו, m.
בצע קריאה רקורסיבית עם build(pre+1, lo, m-1, 2*h+1) ועם build(pre+1+(m-lo), m+1, hi, 2*h+2).
קרא ל־build(0, 0, n-1, 0), ואז הסר את איברי -1 שבסוף והחזר את השאר.

def buildTree(preorder, inorder):
    position = {value: i for i, value in enumerate(inorder)}  # value -> inorder index
    out = [-1] * (2 ** 14 - 1)  # every index of a depth-14 tree is below 2^14-1

    def build(pre, lo, hi, h):
        # preorder[pre] is the root of the subtree that inorder[lo..hi] lists;
        # it goes to index h of the output.
        if lo > hi:
            return
        value = preorder[pre]
        out[h] = value
        m = position[value]
        left_size = m - lo
        build(pre + 1, lo, m - 1, 2 * h + 1)
        build(pre + 1 + left_size, m + 1, hi, 2 * h + 2)

    build(0, 0, len(inorder) - 1, 0)
    last = len(out) - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

מלכודות ומקרי קצה

מתחילים את תת-העץ הימני ב-pre+1+m במקום ב-pre+1+(m-lo). זה עובד כל עוד lo הוא 0, כמו בקריאה העליונה, ונכשל ברגע שטווח מתחיל מאוחר יותר.
משמיטים את הפערים. צומת בן חסר עדיין תופס את מקומו, לכן בדוגמה השנייה התוצאה היא [1, 2, -1, -1, 3], ולא [1, 2, 3].
משאירים ערכי -1 בסוף. החזרה של כל 2^14-1 התאים מוסיפה לדוגמה הראשונה 16376 ערכי -1 מיותרים.
מעתיקים פרוסות של שני המערכים בכל קריאה, מה שמוסיף O(n) לכל רמה. מעבירים טווחי אינדקסים.
ב-Lua וב-R, המערכים מתחילים ב-1. משאירים את המיקומים מבוססי-0 לצורך החישובים, וקוראים את preorder[pre + 1] ואת out[h + 1].

שאלות נפוצות3

למה צריך גם סריקת תחילית וגם סריקה תוך־סדרית כדי לבנות מחדש עץ בינארי?

קדם־סדר לבדו אינו קובע את המבנה. קדם־הסדר [1, 2] מתאים לעץ שבו 2 הוא הילד השמאלי של 1 וגם לעץ שבו הוא הילד הימני. סדר־תוך מכריע: [2, 1] מציב את 2 משמאל, ו־[1, 2] מימין. כאשר הערכים שונים, הצמד מתאר עץ יחיד בדיוק.

מהי סיבוכיות הזמן של בניית עץ בינארי מסריקה בסדר תחילי וסריקה בסדר תוכי?

עם מיפוי מערכים למיקומים בסריקת inorder, זמן הריצה הוא O(n) ונדרש מקום נוסף בנפח O(n). ללא המיפוי, סריקת כל טווח inorder כדי למצוא את השורש שלו עולה O(n·h), ובמקרה של עץ שצורתו כשל מסלול העלות היא O(n²).

האם אפשר לשחזר עץ בינארי באמצעות סריקת קדם וסריקת אחר?

לא באופן כללי. סדר קידומת [1, 2] וסדר סיומת [2, 1] מתאימים גם לילד שמאלי וגם לילד ימני, כי אף אחד מהמעברים לא מציב את השורש בין תתי-העצים שלו. הצמד מספיק רק לעץ בינארי מלא, שבו לכל צומת יש אפס ילדים או שני ילדים.

def buildTree(preorder, inorder):
    # כתבו כאן קוד

בדיקה #1

בדיקה #2

ארגומנטים

preorder = [7, 3, 0, 9, 4, 6]
inorder = [0, 3, 9, 7, 4, 6]

הפלט הצפוי

[7, 3, 4, 0, 9, -1, 6]