Left View of Binary Tree
מקבלים עץ בינארי כמערך 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 = [3, 8, 5, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, 1]
- פלט
- [3, 8, 6, 1]
- הסבר
8הוא עלה, לכן הרמה השלישית והרמה הרביעית מכילות רק את6(אינדקס 6) ואת1(אינדקס 13), שניהם מתחת לילד הימני5. בכל זאת רואים אותם:[3, 8, 6, 1].
- קלט
- root = [10, -1, -1]
- פלט
- [10]
- הסבר
- במיקומים 1 ו-2 מופיע
-1, לכן ל-10אין ילדים והתצוגה מכילה רק את השורש.
- קלט
- root = [1, 2, 3, 4, 5, 6, 7]
- פלט
- [1, 2, 4]
- הסבר
- עץ מלא בן שלוש רמות. המקומות השמאליים ביותר ברמות הם האינדקסים 0, 1 ו-3, שמכילים את
1,2ו-4.
שאלת המשך
רמה d ממלאת את האינדקסים 2^d-1 עד 2^(d+1)-2. האם אפשר לבנות את התצוגה על ידי סריקת הטווחים האלה, בלי תור או רקורסיה? מה העלות של זה במערך מרופד?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
הצומת שרואים ברמה לא תמיד נמצא בצד שמאל. בדוגמה 1, איזה צומת רואים ברמה השלישית, והבן של מי הוא?
קבץ את הצמתים לפי רמה. אם תעבור בכל רמה משמאל לימין, הצומת שאתה מחפש הוא הראשון שתפגוש בה.
עבדו על תור רמה אחת בכל סבב ושמרו את הצומת הראשון בכל סבב. לחלופין, עברו לעומק, העבירו את העומק, עברו שמאלה לפני ימינה, ותעדו צומת כאשר העומק שלו שווה למספר הערכים שתועדו עד כה.
פתרון
מעקב אחר צאצאים שמאליים מהשורש נכשל כשעץ המשנה השמאלי קצר יותר: בדוגמה הראשונה, את הרמות הנמוכות רואים דרך עץ המשנה הימני. צריך את הצומת הראשון בכל רמה. חיפוש לרוחב עובר על כל רמה משמאל לימין; בסריקה לעומק שמתחילה משמאל מגיעים תחילה לצומת השמאלי ביותר בכל רמה.
בחיפוש לרוחב, הצומת הראשון בכל רמה
האינטואיציה
תור שמעובד בסבבים נותן לך את הרמות בזו אחר זו. בתחילת סבב התור מכיל בדיוק רמה אחת, משמאל לימין, כי כל ילד שמתווסף במהלך הסבב נכנס מאחוריה. הוצא את אותו מספר של אינדקסים, הכנס לתור את הילדים של כל אחד מהם, קודם את הילד השמאלי, והשאר את הערך הראשון.
בדוגמה הראשונה הסבבים הם [3], [8, 5], [6] ו-[1], והם משאירים את 3, 8, 6 ו-1. 8 לא מוסיף דבר, כי מיקומי הילדים שלו 3 ו-4 מכילים -1.
כל צומת נכנס לתור ויוצא ממנו פעם אחת: זמן O(n). התור מכיל רמה שלמה, עד 8192 אינדקסים בעץ מלא בן 14 רמות.
אלגוריתם
- התחל תור שמכיל את האינדקס
0, ותשובה ריקה. - כל עוד התור אינו ריק, קבע ש-
sהוא הגודל שלו והסרsאינדקסים. הוסף את הערך של הראשון. - עבור כל אינדקס שהוסר
i, הוסף לתור את2i+1, ואז את2i+2, תוך דילוג על אינדקסים שמעבר לסוף ועל איברים ששווים ל--1.
from collections import deque
def leftView(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 == 0:
view.append(root[i]) # the first 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חיפוש לעומק תחילה, הבן השמאלי קודם
האינטואיציה
עוברים בעץ בסדר עומק, בתת-העץ השמאלי לפני הימני, ומעבירים את העומק של כל צומת. הצומת הראשון שהמעבר מגיע אליו בעומק d הוא השמאלי ביותר ברמה d. ניקח את הצומת השמאלי ביותר x ברמה כלשהי ואת כל צומת y שנמצא מימינו: בצומת האחרון שבו המסלולים שלהם מתפצלים, x פונה שמאלה ו-y ימינה, והמעבר מסיים את הענף השמאלי לפני שהוא פונה ימינה.
המעבר מתקדם למטה רמה אחת בכל פעם, ולכן כשהוא מגיע לראשונה לעומק d, התשובה מכילה בדיוק d ערכים. מתעדים צומת כאשר d שווה לאורך התשובה; אין צורך בקבוצה של עומקים שכבר נצפו.
מבקרים בכל צומת פעם אחת, בזמן O(n), והזיכרון מכיל קריאה אחת לכל רמה, 14 לכל היותר במקרה הזה. גרסת R מנהלת מחסנית משלה ודוחפת את הצומת הימני לפני השמאלי.
אלגוריתם
- צרו תשובה ריקה וקראו ל־
visit(0, 0). - בתוך
visit(i, d), חזרו מיד אםiנמצא מחוץ למערך או אםroot[i]הוא-1. - אם
dשווה לאורך התשובה, הסריקה הגיעה לרמהdבפעם הראשונה: הוסיפו אתroot[i]. - קראו ל־
visit(2i+1, d+1), ואז ל־visit(2i+2, d+1). - החזירו את התשובה לאחר שהקריאה הראשונה מסתיימת.
def leftView(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])
# Left before right, so the leftmost node of every level comes first.
visit(2 * i + 1, depth + 1)
visit(2 * i + 2, depth + 1)
visit(0, 0)
return view
מלכודות ומקרי קצה
- מעקב רק אחר הילדים השמאליים מהשורש. בדוגמה הראשונה, הדבר נעצר ב־
8ומפספס את6ואת1. - קריאת התא הראשון בכל רמה,
root[2^d-1]. בדוגמה הראשונה, התא הראשון ברמה השלישית, באינדקס 3, מכיל את-1, בעוד שהצומת היחיד שלה נמצא באינדקס 6. - ביקור תחילה בילד הימני בסריקה לעומק. כך, הצומת הראשון שפוגשים בכל רמה הוא הימני ביותר.
- קריאת ילד ללא בדיקת גבולות. ל־
1שבאינדקס 13 יש מקומות לילדים באינדקסים 27 ו־28, מעבר לסוף המערך בן 14 האיברים.
שאלות נפוצות3
האם התצוגה השמאלית זהה לגבול השמאלי של עץ?
לא. הגבול השמאלי הוא מסלול: הוא מתחיל בילד השמאלי של השורש, פונה שמאלה כשאפשר, אחרת ימינה, ונעצר לפני עלה. התצוגה השמאלית כוללת צומת אחד בכל רמה מכל ענף. בדוגמה הראשונה הגבול ריק, מכיוון ש־8 הוא עלה, אבל התצוגה מציגה את 8, 6 ו־1.
מהי סיבוכיות הזמן והמרחב של המבט השמאלי?
שני הפתרונות עוברים על כל צומת פעם אחת, ולכן זמן הריצה הוא O(n). התור של החיפוש לרוחב מכיל רמה שלמה, בערך מחצית מהצמתים בעץ מלא. ההליכה שמתחילה משמאל מחזיקה קריאה אחת לכל רמה, O(h) עבור h רמות.
איך משנים את הפתרון כדי לקבל את התצוגה הנכונה?
בגרסת החיפוש לרוחב, שומרים את הערך האחרון בכל סבב במקום את הראשון. בגרסת החיפוש לעומק, מבקרים בצומת הימני לפני הצומת השמאלי; הצומת הראשון שהמעבר מגיע אליו בכל רמה הוא אז הימני ביותר.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def leftView(root):
# כתבו כאן את הקודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנט
root = [3, 8, 5, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, 1]
הפלט הצפוי
[3, 8, 6, 1]