Invert Binary Tree

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

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

קלסריקת עצים

+10

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

הפוך את העץ: החלף בין הילד השמאלי לילד הימני של כל צומת, כך שהעץ כולו יהפוך לתמונת מראה של עצמו. החזר את העץ ההפוך באותה צורה, ללא ערכי -1 בסוף.

פונקציה

invertTree(tree: integer-array) → integer-array

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

אילוצים

1 ≤ tree.length ≤ 16383
כל tree[i] הוא -1 או ערך שמקיים 0 ≤ tree[i] ≤ 1000.
tree[0] לעולם אינו -1, ולכן יש בעץ לפחות צומת אחד.
ייתכן שבמערך יהיו רשומות נוספות של -1 אחרי הצומת האחרון.
גם שני הצאצאים של מקום ריק ריקים, והעומק הוא לכל היותר 14.

דוגמאות

קלט: tree = [5, 3, 8, 1, 4, -1, 9]
פלט: [5, 8, 3, 9, -1, 4, 1]
הסבר: הילדים של השורש 3 ו־8 מחליפים מקומות. מתחתיהם, 1 ו־4 שמתחת ל־3 חוזרים בתור 4 ו־1, ול־8, שהיה לו רק ילד ימני 9, יש אותו עכשיו בצד שמאל.

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

קלט: tree = [1, -1, -1]
פלט: [1]
הסבר: צומת יחיד הוא המראה של עצמו. שתי הרשומות -1 הן ריפוד, והתשובה משמיטה כל -1 שבסוף.

שאלת המשך

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

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

רקורסיה שממקמת כל צומת באינדקס המשוקף שלו

האינטואיציה

ראשית, איך נעים במערך. לצומת באינדקס i יש בן שמאלי באינדקס 2*i+1 ובן ימני באינדקס 2*i+2. בן נחשב לצומת אמיתי רק אם האינדקס שלו נמצא בתוך המערך והערך שם אינו -1. במערך [5, 3, 8, 1, 4, -1, 9] לשורש 5 יש את 3 ואת 8 באינדקסים 1 ו-2, ול-8 שבאינדקס 2 יש מקום שמאלי ריק באינדקס 5 ואת 9 באינדקס 6.

ועכשיו, ההיפוך. השורש נשאר באינדקס 0. תת-העץ השמאלי של צומת הופך לתת-העץ הימני של העותק ההפוך שלו, ותת-העץ הימני הופך לשמאלי. לכן, אם הצומת שבאינדקס src ממוקם באינדקס dst בתשובה, הבן השמאלי שלו ימוקם באינדקס 2*dst+2 והבן הימני שלו באינדקס 2*dst+1. כתבו place(src, dst): העתיקו את הערך, ואז קראו ל-place(2*src+1, 2*dst+2) ול-place(2*src+2, 2*dst+1). מקום ריק חוזר מיד. בדוגמה הראשונה, ה-3 שבאינדקס 1 ממוקם באינדקס 2, ולכן הבן השמאלי שלו, 1, ממוקם באינדקס 6, והבן הימני שלו, 4, באינדקס 5.

צומת לעולם אינו משנה רמה, ולכן האינדקס שלו לאחר ההיפוך נשאר באותה רמה שבה היה קודם. עגלו את האורך כלפי מעלה עד למספר שלם של רמות (1, 3, 7, 15, ...), מלאו את מספר המקומות הזה ב--1, ובסוף הסירו את ערכי ה--1 שבסוף המערך. בדוגמה השנייה, האורך 4 מעוגל כלפי מעלה ל-7, וכך נשאר מקום ל-6 באינדקס 6.

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

אלגוריתם

עגל את האורך כלפי מעלה ל-size = 2^k - 1 ומלא פלט בגודל הזה בערכי -1.
כתוב את place(src, dst): אם src נמצא מעבר לסוף או ש-tree[src] הוא -1, החזר.
אחרת הגדר out[dst] = tree[src], ואז קרא ל-place(2*src+1, 2*dst+2) ול-place(2*src+2, 2*dst+1).
קרא ל-place(0, 0), הסר את ערכי -1 שבסוף והחזר את הפלט.

def invertTree(tree):
    n = len(tree)
    size = 1
    while size < n:  # round up to whole levels, so every mirrored index fits
        size = 2 * size + 1
    out = [-1] * size

    def place(src, dst):
        if src >= n or tree[src] == -1:
            return
        out[dst] = tree[src]
        place(2 * src + 1, 2 * dst + 2)  # the left subtree goes to the right
        place(2 * src + 2, 2 * dst + 1)  # the right subtree goes to the left

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

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

האינטואיציה

אותם זוגות פועלים גם ללא רקורסיה. מכניסים לתור את (0, 0): השורש, והמיקום שאליו הוא עובר. מוציאים זוג (src, dst) מראש התור, מעתיקים את tree[src] אל out[dst], ומכניסים לתור כל ילד קיים עם יעד מוחלף: הילד השמאלי 2*src+1 עם 2*dst+2, והילד הימני 2*src+2 עם 2*dst+1.

זוהי ההיפוך האיטרטיבי הקלאסי. כשעובדים עם אובייקטים של צמתים, מוציאים צומת מהתור, מחליפים בין שני ילדיו ומכניסים אותם לתור. כאן כותבים את ההחלפה באינדקס היעד במקום זאת, כי המערך אינו יכול להחליף שני תתי-עצים שלמים בצעד אחד. כל צומת קיים נכנס לתור פעם אחת, כשהוא נושא את המיקום המדויק שלו, ולכן הפלט מכיל בסופו של דבר כל צומת במיקום המראה שלו. בדוגמה הראשונה הזוגות שמתקבלים הם (0, 0), (1, 2), (2, 1), (3, 6), (4, 5), (6, 3).

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

אלגוריתם

עגלו את האורך כלפי מעלה לרמות שלמות ומלאו פלט בגודל הזה בערכי -1.
הכניסו את הזוג (0, 0) לתור.
הוציאו זוג (src, dst) מחזית התור והגדירו out[dst] = tree[src].
הכניסו לתור את (2*src+1, 2*dst+2) ואת (2*src+2, 2*dst+1) עבור כל ילד שנמצא בתוך המערך ואינו -1.
כשהתור מתרוקן, הסירו את ערכי -1 שבסוף והחזירו את הפלט.

def invertTree(tree):
    n = len(tree)
    size = 1
    while size < n:  # round up to whole levels, so every mirrored index fits
        size = 2 * size + 1
    out = [-1] * size
    queue = [(0, 0)]  # pairs: index in tree, index of its mirrored spot in out
    head = 0
    while head < len(queue):
        src, dst = queue[head]
        head += 1
        out[dst] = tree[src]
        left, right = 2 * src + 1, 2 * src + 2
        if left < n and tree[left] != -1:
            queue.append((left, 2 * dst + 2))  # the left child goes to the right
        if right < n and tree[right] != -1:
            queue.append((right, 2 * dst + 1))  # the right child goes to the left
    last = size - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

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

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

החלפת tree[2*i+1] ו-tree[2*i+2] במקום. כך מחליפים בין שני ערכים, אבל לא בין תתי-העצים שמתחתיהם. החלפת האינדקסים 1 ו-2 בדוגמה הראשונה משאירה את 1 ואת 4 תלויים מתחת ל-8.
יצירת פלט באורך זהה לקלט. צומת משוקף יכול להימצא אחרי האינדקס האחרון בקלט, כמו 6 בדוגמה השנייה. יש להקצות לפלט מקום לרמות שלמות.
שכחה לקצץ את הפלט. התשובה אינה מסתיימת ב--1, גם במקרה של קלטים מרופדים וגם במקרה של עצים שהשיקוף שלהם מסתיים לפני שהקלט מסתיים.
היפוך של המערך כולו. כך מתערבבות הרמות: העלה האחרון יהפוך לשורש.
דילוג על בדיקת הגבולות. אינדקס של צאצא יכול להיות מעבר לסוף הקלט, כי ייתכן שהמערך מסתיים מיד אחרי הצומת האחרון.
בלבול לגבי ההיסט ב-Lua וב-R, שבהן המערכים מתחילים ב-1. יש להשאיר את האינדקסים מבוססי-0 עבור החישוב 2*i+1 ולקרוא את tree[i + 1].

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

מה המשמעות של היפוך עץ בינארי?

היפוך של עץ בינארי הופך אותו לתמונת מראה: בכל צומת תתי־העצים השמאלי והימני מחליפים מקומות. השורש נשאר במקומו, העלה השמאלי ביותר הופך לימני ביותר, ושרשרת שמאלית הופכת לשרשרת ימנית. היפוך פעמיים מחזיר את העץ המקורי.

מהי סיבוכיות הזמן של היפוך עץ בינארי?

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

איך הופכים עץ בינארי בלי רקורסיה?

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

def invertTree(tree):
    # כתבו כאן קוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנט

tree = [5, 3, 8, 1, 4, -1, 9]

הפלט הצפוי

[5, 8, 3, 9, -1, 4, 1]