Binary Tree Right Side View
המערך root מכיל עץ בינארי. השורש נמצא באינדקס 0, הילדים של הצומת באינדקס i נמצאים באינדקסים 2*i+1 (שמאל) ו-2*i+2 (ימין), -1 מציין מקום ריק, וייתכן שבסוף יופיעו ערכי -1 נוספים.
הביטו בעץ מצד ימין. בכל רמה תוכלו לראות בדיוק צומת אחד, את זה שנמצא הכי ימינה, והוא מסתיר את השאר. רשמו את הערכים האלה, מרמת השורש ועד לרמה העמוקה ביותר.
פונקציה
- rootinteger-array
- העץ בסדר ערימה, כאשר -1 מציין מקום ריק
- מחזירהinteger-array
- הערך הימני ביותר בכל רמה, החל מהרמה העליונה
אילוצים
1 ≤ root.length ≤ 32767- כל
root[i]הוא-1או ערך המקיים0 ≤ root[i] ≤ 104. - ערכי הצמתים שונים זה מזה.
root[0]לעולם אינו-1, ולכן לעץ יש לפחות צומת אחד.- ייתכן שבמערך יופיעו ערכי
-1נוספים אחרי הצומת האחרון. - שני הילדים של מקום ריק גם הם ריקים, ולעץ יש לכל היותר
14רמות.
דוגמאות
- קלט
- root = [5, 2, 9, 7, 4, -1, 1, -1, 3]
- פלט
- [5, 9, 1, 3]
- הסבר
- מימין רואים את
5, את9ואת1(אינדקס 6). ברמה הרביעית יש רק את3, באינדקס 8 מתחת ל-7בתת-העץ השמאלי. שום דבר מימין לא מגיע לעומק הזה, ולכן3גלוי.
- קלט
- root = [6, 0, -1, 8, -1, -1, -1]
- פלט
- [6, 0, 8]
- הסבר
- העץ הוא שרשרת של צמתים שמאליים:
6,0,8. בכל רמה יש צומת אחד, כך שרואים את שלושתם, אף שאף אחד מהם אינו צומת ימני.
- קלט
- root = [42]
- פלט
- [42]
- הסבר
- מערך באורך 1: לשורש
42אין כלל מקומות לילדים, והתצוגה היא הערך האחד הזה.
שאלת המשך
איך תקבלו את מבט הצד הימני של עץ שבו לכל צומת יכול להיות כל מספר של ילדים, המאוחסנים כרשימה משמאל לימין?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
ירידה לאורך הילדים הימניים של דוגמה 1 נותנת
5, 9, 1ונעצרת. בתשובה יש ערך רביעי. מאיפה הוא מגיע?קבץ את הצמתים לפי עומק במקום לפי צד. כתוב כל רמה משמאל לימין: היכן ברשימה הזו נמצא הצומת שאדם בצד ימין יראה?
שמרו רשימה
view. עברו לעומק תחילה, עם העומק, ילד ימני לפני ילד שמאלי, והוסיפו צומת כאשר העומק שלו שווה לאורך שלview. גם תור שפועל ברמה אחת בכל סבב מתאים: הוסיפו את הצומת האחרון בכל סבב.
פתרון
אתה רואה את הצומת הימני ביותר בכל רמה, והוא לא חייב להיות בן ימני: הערך האחרון בדוגמה 1 נמצא בתת-העץ השמאלי. חיפוש לרוחב הופך את הצומת הזה לאחרון בכל סבב; בסריקה לעומק שמתחילה מימין נתקלים בו לפני כל צומת אחר ברמה שלו.
בחיפוש לרוחב, הצומת האחרון בכל רמה
האינטואיציה
עבדו על העץ רמה אחת בכל סבב. כשסבב מתחיל, התור מכיל בדיוק רמה אחת, משמאל לימין, ולכן האינדקס האחרון שמוציאים מהתור בסבב הוא הצומת הימני ביותר באותה רמה, והערך שלו נכנס לתשובה.
בדוגמה 1 הסבבים הם [5], [2, 9], [7, 4, 1] ו-[3], והאיברים האחרונים בהם נותנים את 5, 9, 1, 3. הרמה היא שקובעת, לא הצד: 3 נמצא בתת-העץ השמאלי, אבל הוא לבדו ברמה שלו.
כל אינדקס נכנס לתור ויוצא ממנו פעם אחת, ולכן זמן הריצה הוא O(n). התור גדל עד לרמה הרחבה ביותר, O(n) במקרה הגרוע ביותר.
אלגוריתם
- הוסף לתור את האינדקס של השורש
0. - התחל סבב על ידי שמירת אורך התור
s. - הוצא מהתור
sאינדקסים. עבור כל אינדקסi, הוסף לתור את2i+1ואז את2i+2אם הם קטנים מאורך המערך ואינם-1. - הוסף את הערך של האינדקס האחרון שהוצא מהתור בסבב.
- חזור על הפעולה עד שהתור ריק, ואז החזר את התשובה.
from collections import deque
def rightSideView(root):
n = len(root)
view = []
queue = deque([0]) # node indexes; the root is never empty
while queue:
size = len(queue) # exactly the nodes of the current level
for j in range(size):
i = queue.popleft()
if j == size - 1:
view.append(root[i]) # the last node of this level
for child in (2 * i + 1, 2 * i + 2):
if child < n and root[child] != -1:
queue.append(child)
return viewחיפוש לעומק תחילה, הילד הימני קודם
האינטואיציה
עברו בעומק תחילה, נסו את הילד הימני לפני השמאלי, ושמרו את העומק, 0 בשורש. בפעם הראשונה שהמעבר מגיע לעומק d, התשובה מכילה בדיוק d ערכים. הוסיפו אז את ערך הצומת והתעלמו מכל צומת מאוחר יותר באותה רמה.
הצומת הראשון הזה הוא הימני ביותר: בכל מקום שבו שני מסלולים לרמה מתפצלים, המעבר עוקב אחר הענף הימני עד לתחתית לפני שהוא חוזר לאחור אל הענף השמאלי. בדוגמה 1 המעבר מבקר ב־5, 9, 1, 2, 4, 7, 3: הוא מדלג על 2, 4 ו־7, שכבר יש להם ערך בעומק שלהם, ומוסיף את 3.
כל צומת מבוקר פעם אחת, בזמן O(n), עם קריאה אחת לכל רמה במחסנית, 14 לכל היותר.
אלגוריתם
- התחילו עם תשובה ריקה והשורש בעומק 0.
- דלגו על אינדקס שנמצא אחרי סוף המערך או מכיל
-1. - כאשר אורך התשובה שווה לעומק, הוסיפו את הערך: הסריקה הגיעה לרמה חדשה, והיא הגיעה אליה מימין.
- בצעו רקורסיה תחילה על הילד הימני
2i+2, ואז על הילד השמאלי2i+1, כל אחד ברמה אחת עמוקה יותר. - החזירו את התשובה.
def rightSideView(root):
n = len(root)
view = []
def visit(i, depth):
if i >= n or root[i] == -1:
return
if depth == len(view): # the first node met on this level
view.append(root[i])
# Right before left, so the rightmost node of every level comes first.
visit(2 * i + 2, depth + 1)
visit(2 * i + 1, depth + 1)
visit(0, 0)
return view
מלכודות ומקרי קצה
- מעקב רק אחר הילדים הימניים מהשורש. דוגמה 1 נותנת אז
[5, 9, 1]ומפספסת את3; דוגמה 2 נותנת[6]. - קריאת התא האחרון בכל רמה,
root[2^(d+1)-2]. בדוגמה 2, האינדקס 6 מכיל את-1; הצומת הגלוי הוא8באינדקס 3. - דילוג על בדיקת האורך במקום של ילד. בדוגמה 1,
3הוא האיבר האחרון, ולכן מקומות הילדים שלו 17 ו-18 אינם קיימים. - הוספת הילד הימני לתור תחילה, תוך שמירת הצומת האחרון בכל סבב. כך מתקבלת התצוגה משמאל,
[5, 2, 7, 3]. - מתן אפשרות לצמתים מאוחרים יותר לדרוס צמתים מוקדמים יותר בסריקה מימין לשמאל, שגם היא מניבה את התצוגה משמאל.
שאלות נפוצות3
מהי סיבוכיות הזמן וסיבוכיות המקום של תצוגת הצד הימני של עץ בינארי?
הזמן הוא O(n) עבור n צמתים, ואף פתרון לא יכול לדלג על צמתים, מכיוון שהצומת הימני ביותר ברמה עשוי להימצא בכל מקום. המקום הוא O(w) עבור התור, כאשר w היא הרמה הרחבה ביותר, או O(h) עבור מעבר תחילה ימינה בעץ בעל h רמות.
האם חיפוש לעומק שמתחיל משמאל יכול לפתור את זה?
כן, אם תדרוס את הערך הראשון במקום לשמור אותו. מעבר שמתחיל משמאל פוגש את הצמתים בכל רמה משמאל לימין, אז שמור את הערך של כל צומת בעומק שלו, ותן לצמתים מאוחרים יותר להחליף ערכים מוקדמים יותר. בכל עומק יישאר הערך הימני ביותר. הסיבוכיות עדיין O(n), אבל מתבצעת כתיבה אחת לכל צומת.
האם כדאי להשתמש כאן בחיפוש לרוחב או בחיפוש לעומק?
שניהם לינאריים. חיפוש לרוחב פועל לפי ההגדרה, רמה אחת בכל סבב. חיפוש לעומק שומר רק את הנתיב הנוכחי, וכך חוסך זיכרון בעץ רחב, והצורה הרקורסיבית שלו קצרה בכמה שורות.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def rightSideView(root):
# כתבו כאן קודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנט
root = [5, 2, 9, 7, 4, -1, 1, -1, 3]
הפלט הצפוי
[5, 9, 1, 3]