Binary Tree Level Order Traversal
המערך tree מכיל עץ בינארי. השורש נמצא באינדקס 0, הילדים של הצומת באינדקס i נמצאים באינדקסים 2*i+1 (שמאל) ו־2*i+2 (ימין), -1 מסמן מקום ריק, וייתכן שבסוף יופיעו ערכי -1 נוספים.
החזר את ערכי הצמתים לפי רמות: רשימה אחת לכל רמה, מהשורש ועד לרמה העמוקה ביותר, כשבכל רשימה הערכים מסודרים משמאל לימין.
פונקציה
- treeinteger-array
- העץ בסדר ערימה, עם -1 עבור מקום ריק
- מחזירהinteger-2d-array
- רשימה אחת של ערכים לכל רמה, מהרמה העליונה תחילה, כל אחת משמאל לימין
אילוצים
1 ≤ tree.length ≤ 32767- כל
tree[i]הוא-1או ערך שמקיים0 ≤ tree[i] ≤ 1000. tree[0]לעולם אינו-1, ולכן לעץ יש לפחות צומת אחד.- המערך עשוי להסתיים בערכי
-1נוספים אחרי הצומת האחרון. - גם שני הצאצאים של מקום ריק ריקים, והעומק הוא לכל היותר
14.
דוגמאות
- קלט
- tree = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]
- פלט
- [[4], [9, 2], [6, 8, 5], [3]]
- הסבר
- האינדקס 3 ריק, לכן ל־
9יש רק ילד ימני,6. הרמה השלישית כוללת את6,8,5, ואת3שבאינדקס 9, מתחת ל־6, שנמצא לבדו ברמה הרביעית.
- קלט
- tree = [7, -1, -1]
- פלט
- [[7]]
- הסבר
- שני הילדים של השורש הם
-1, לכן העץ הוא הצומת היחיד7ויש לו רמה אחת.
- קלט
- tree = [1, 3, -1, 5, -1, -1, -1]
- פלט
- [[1], [3], [5]]
- הסבר
- לכל צומת יש רק ילד שמאלי:
3באינדקס 1 ו־5באינדקס 3. בכל רמה יש ערך אחד, והערכים-1שבסוף אינם מוסיפים דבר.
שאלת המשך
האם תוכל להחזיר את הרמות בסדר זיגזג, הראשונה משמאל לימין, השנייה מימין לשמאל, וכן הלאה, בלי למיין אף רמה?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
הילדים באינדקס
iנמצאים ב-2*i+1וב-2*i+2. אם תמיד מבקרים קודם בצמתים הקרובים ביותר לשורש, וביניהם עוברים משמאל לימין, באיזה סדר פוגשים את הצמתים?תור מחזיר צמתים לפי הסדר שבו הכנסת אותם. אם מוסיפים את הילדים של צומת כשמוציאים אותו, הצמתים יוצאים רמה אחת בכל פעם. מה שנותר הוא לציין היכן רמה אחת מסתיימת והבאה מתחילה.
בתחילת כל סיבוב, התור מכיל בדיוק רמה אחת. קרא את הגודל שלה
s, הוצאsצמתים לרשימה חדשה, והוסף את הילדים שלהם, קודם את השמאלי, תוך דילוג על-1ועל אינדקסים שמעבר לסוף. עצור כשהתור ריק.
פתרון
כל רמה צריכה להתקבל כרשימה משלה, משמאל לימין. חיפוש לרוחב באמצעות תור מבקר בצמתים בסדר הזה, ובתחילת כל סבב התור מכיל בדיוק רמה אחת, ולכן הגודל שלו מציין כמה צמתים לקחת. גם מעבר לעומק שעוקב אחר העומק של כל צומת יעבוד.
חיפוש לעומק, מסודר לפי עומק
האינטואיציה
עוברים על העץ בחיפוש לעומק, מעבירים לכל צומת את העומק שלו, 0 עבור השורש, ושומרים רשימה אחת לכל עומק. צומת בעומק d מוסיף את הערך שלו לרשימה d, ויוצר את הרשימה אם זהו הצומת הראשון ברמה שלו.
כל רשימה מתקבלת משמאל לימין, כי המעבר מסיים לעבור על תת-העץ השמאלי של צומת לפני שהוא נכנס לתת-העץ הימני שלו. מבין שני צמתים באותה רמה, מגיעים קודם לזה שהמסלול אליו פונה שמאלה במקום שבו המסלולים מתפצלים. בדוגמה 1, סדר הביקור 4, 9, 6, 3, 2, 8, 5 ממלא את [4], [9, 2], [6, 8, 5], [3].
מבקרים בכל צומת פעם אחת: זמן O(n), כשהרקורסיה מגיעה לעומק העץ, עד 14 רמות.
אלגוריתם
- צור רשימה ריקה של רמות.
- בקר בשורש בעומק 0.
- בצומת
iבעומקd, עצור אםiנמצא אחרי סוף המערך או אםtree[i]הוא-1. - אם יש רק
dרשימות, הוסף רשימה ריקה. הוסף אתtree[i]לרשימהd. - בקר ב-
2i+1, ואז ב-2i+2, בשניהם בעומקd+1.
def levelOrder(tree):
n = len(tree)
levels = []
def visit(i, depth):
if i >= n or tree[i] == -1:
return
if depth == len(levels): # the first node seen on this level
levels.append([])
levels[depth].append(tree[i])
# Left before right, so every level fills from left to right.
visit(2 * i + 1, depth + 1)
visit(2 * i + 2, depth + 1)
visit(0, 0)
return levelsחיפוש לרוחב, רמה אחת בכל סבב
האינטואיציה
הוצא צומת מהתור והכנס אליו את ילדיו, קודם את השמאלי. רמה d+1 נכנסת רק כשהרמה d יוצאת, ולכן הצמתים יוצאים רמה אחר רמה, משמאל לימין.
כדי לחלק את הזרם הזה לרמות, קרא את גודל התור בתחילת סבב. הרמה הקודמת כבר יצאה, ועדיין לא הגיע אף צומת מהרמה הבאה, ולכן התור מכיל בדיוק את הרמה הנוכחית. הוצא מספר כזה של צמתים לשורה אחת; ילדיהם יחכו לסבב הבא. בדוגמה 1 הסבבים מוציאים 1, 2, 3 ו־1 צמתים.
כל צומת נכנס לתור ויוצא ממנו פעם אחת: זמן O(n). התור מכיל בערך רמה אחת, ולכל היותר 8,192 צמתים ברמה העמוקה ביותר של עץ מלא בן 14 רמות.
אלגוריתם
- הכניסו את האינדקס
0של השורש לתור. - כל עוד התור אינו ריק, קראו את גודלו
sוהתחילו שורה ריקה. - הוציאו
sאינדקסים. עבור כל אינדקסi, הוסיפו אתtree[i]לשורה. - הוסיפו לתור את
2i+1, ואז את2i+2, כאשר האינדקס נמצא בתוך המערך ואינו מכיל-1. - הוסיפו את השורה לתשובה והתחילו את הסבב הבא.
from collections import deque
def levelOrder(tree):
n = len(tree)
levels = []
queue = deque([0]) # node indexes; the root is never empty
while queue:
row = []
for _ in range(len(queue)): # exactly the nodes of the current level
i = queue.popleft()
row.append(tree[i])
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
queue.append(child)
levels.append(row)
return levels
מלכודות ומקרי קצה
- קריאת הגודל של התור בזמן שרוקנים אותו. ב־
while (j < queue.length)האורך גדל כשילדים מגיעים, ולכן הרמה הבאה גולשת לשורה הנוכחית. - הוספת הילד הימני לפני הילד השמאלי, או ביקור בתת־העץ הימני תחילה. הרמה השנייה בדוגמה 1 נקראת אז
[2, 9]. - דילוג על בדיקת הגבול
child < n. הילדים של הצמתים העמוקים ביותר נמצאים מעבר לסוף המערך. - הסרה מתחילתה של רשימת מערך רגילה, שבשפות רבות מזיזה את התור כולו בכל פעם. השתמשו בתור אמיתי או באינדקס ראש.
- התייחסות אל
-1כאל צומת. הוא אף פעם לא נכנס לשורה או לתור:[7, -1, -1]נותן[[7]], ולא[[7], []].
שאלות נפוצות3
מהי סיבוכיות הזמן של מעבר לפי רמות בעץ בינארי?
שני הפתרונות מבקרים בכל צומת פעם אחת: זמן של O(n) עבור n צמתים. התשובה מכילה n ערכים, ולכן המקום הוא O(n). מלבד זאת, התור מכיל בערך את הרמה הרחבה ביותר, והרקורסיה את גובה העץ.
איך יודעים היכן מסתיימת רמה אחת בחיפוש לרוחב?
קראו את גודל התור בתחילת כל סבב והוציאו ממנו בדיוק את מספר הצמתים הזה. גם שתי דרכים אחרות עובדות: לשמור את הרמה הנוכחית ואת הרמה הבאה בשתי רשימות נפרדות, או לדחוף סמן לתור אחרי כל רמה.
המערך כבר מאוחסן לפי רמות. למה לא לקרוא אותו בפרוסות?
בפורמט הזה זה עובד כך: רמה d, כשהשורש נמצא ב־0, ממלאת את האינדקסים 2^d-1 עד 2^(d+1)-2, לכן אוספים את הערכים הלא־ריקים של כל טווח עד שמגיעים לטווח שאין בו ערכים. בראיונות בדרך כלל מעבירים אובייקטים של צמתים עם מצביעים במקום זאת, ורק התור נשאר זהה גם בצורה הזאת.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def levelOrder(tree):
# כתבו כאן קודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנט
tree = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]
הפלט הצפוי
[[4], [9, 2], [6, 8, 5], [3]]