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]]
- הסבר
- לשורש
4יש ילדים9ו-2באינדקסים 1 ו-2. אינדקס 3 ריק, ולכן הרמה השלישית היא6(אינדקס 4, מתחת ל-9), ואז8ו-5(אינדקסים 5 ו-6, מתחת ל-2). ה-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שבסוף אינם מוסיפים דבר.
+15 בדיקות נסתרות בשליחה
שאלת המשך
האם אפשר להחזיר את הרמות בסדר זיגזג, את הראשונה משמאל לימין, את השנייה מימין לשמאל, וכן הלאה, בלי למיין אף רמה?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
הילדים של האינדקס
iנמצאים ב-2*i+1וב-2*i+2. אם תמיד מבקרים קודם בצמתים הקרובים ביותר לשורש, ומתקדמים משמאל לימין ביניהם, באיזה סדר פוגשים את הצמתים?תור מחזיר צמתים לפי הסדר שבו הכנסת אותם. אם מוסיפים את הילדים של צומת כשמוציאים את הצומת, הצמתים יוצאים רמה אחת בכל פעם. מה שנותר הוא לסמן היכן רמה אחת מסתיימת והבאה מתחילה.
בתחילת כל סיבוב התור מכיל בדיוק רמה אחת. קרא את גודלו
s, הוצאsצמתים לרשימה חדשה, והוסף את ילדיהם, תחילה את השמאלי, תוך דילוג על-1ועל אינדקסים שמעבר לסוף. עצור כשהתור ריק.
פתרון
כל רמה צריכה להופיע כרשימה נפרדת, בסדר משמאל לימין. חיפוש לרוחב באמצעות תור מבקר בצמתים בדיוק בסדר הזה. הרעיון הנוסף היחיד הוא לדעת היכן רמה מסתיימת: בתחילת כל סבב, התור מכיל את כל הרמה הנוכחית ולא שום דבר אחר, ולכן הגודל שלו אומר לך כמה צמתים לקחת. גם מעבר לעומק עובד, כל עוד הוא שומר את העומק של כל צומת ומתקדם תחילה שמאלה ואז ימינה.
חיפוש לעומק תחילה, מסודר לפי עומק
האינטואיציה
ראשית, נבין איך לנוע במערך. הילד השמאלי של האינדקס i נמצא ב־2i+1, והילד הימני נמצא ב־2i+2. ילד חסר כשהאינדקס שלו מחוץ לגבולות המערך או כשהערך בו הוא -1. בדוגמה 1 הילדים של 9 (אינדקס 1) נמצאים באינדקסים 3 ו־4, שמכילים -1 ו־6, ולכן ל־9 יש רק ילד ימני.
כעת נעבור על העץ בסריקת עומק, ונעביר לכל צומת את עומקו, כאשר עומק השורש הוא 0. נשמור רשימה אחת לכל עומק. כשנגיע לצומת בעומק d, נוסיף את ערכו לרשימה d; אם יש עד כה רק d רשימות, זהו הצומת הראשון ברמה חדשה, ולכן נתחיל קודם רשימה חדשה.
למה כל רמה מתקבלת משמאל לימין? הסריקה מסיימת לעבור על כל תת־העץ השמאלי של צומת לפני שהיא נכנסת לתת־העץ הימני. ניקח שני צמתים באותה רמה: במקום שבו המסלולים שלהם מהשורש מתפצלים, אחד פונה שמאלה והשני ימינה, והסריקה מגיעה קודם לצומת השמאלי. בדוגמה 1 הסדר הוא 4, 9, 6, 3, 2, 8, 5, וכך הרשימות מתמלאות: [4], [9, 2], [6, 8, 5], [3].
מבקרים בכל צומת פעם אחת, לכן זמן הריצה הוא O(n) עבור n צמתים, והרשימות מכילות n ערכים. עומק הרקורסיה הוא כעומק העץ בלבד, עד 15 רמות במקרה הזה. גרסת R משתמשת במקום זאת במחסנית מפורשת: היא דוחפת את הילד הימני לפני הילד השמאלי, כך שהשמאלי נשלף ראשון, ואז מקבצת את הערכים לפי עומק באמצעות split.
אלגוריתם
- צור רשימה ריקה של רמות.
- בקר בשורש בעומק 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 יוצא ממנו, ולכן כל הצמתים ברמה d יוצאים לפני כל צומת ברמה d+1, ובתוך כל רמה הצמתים יוצאים משמאל לימין.
כך מתקבל רצף אחד של ערכים לפי סדר הרמות. כדי לחלק אותו לרמות, קוראים את גודל התור בתחילת כל סבב. באותו רגע התור מכיל בדיוק את הרמה הנוכחית: הרמה הקודמת כבר יצאה ואף צומת מהרמה הבאה עדיין לא נכנס. מוציאים מספר זה של צמתים לרשימה אחת. הילדים שהם מוסיפים שייכים לסבב הבא.
בדוגמה 1 התור מתחיל כך: [4]: מוציאים צומת אחד, שורה [4], ו-9, 2 נכנסים. מוציאים 2 צמתים, שורה [9, 2], ו-6, 8, 5 נכנסים. מוציאים 3, שורה [6, 8, 5], ו-3 נכנס. מוציאים 1, שורה [3], והתור ריק.
כל צומת נכנס לתור ויוצא ממנו פעם אחת, לכן זמן הריצה הוא O(n). התור מכיל לכל היותר בערך רמה אחת, עד 16384 צמתים ברמה העמוקה ביותר של עץ מלא בעומק 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כאל ערך. מקום ריק אינו צומת, ולכן הוא לעולם אינו נכנס לשורה או לתור. - שכחת בדיקת הגבול. הילדים של הצמתים העמוקים ביותר עשויים להיות מעבר לסוף המערך, לכן בדקו
child < nלפני קריאתtree[child]. - החזרת רמות ריקות. ערכי
-1שבסוף אינם מכילים צמתים, ולכן התשובה עבור[7, -1, -1]היא[[7]], ולא[[7], []].
שאלות נפוצות4
מהי סיבוכיות הזמן של מעבר לפי סדר רמות בעץ בינארי?
גם הפתרון בחיפוש לרוחב וגם הפתרון בחיפוש לעומק מבקרים בכל צומת פעם אחת, ולכן זמן הריצה שלהם הוא O(n) עבור n צמתים. התשובה עצמה מכילה n ערכים, ולכן צריכת המקום היא O(n). נוסף על כך, התור מכיל לכל היותר בערך את מספר הצמתים ברמה הרחבה ביותר, והקריאות הרקורסיביות מגיעות לכל היותר לגובה העץ.
איך יודעים היכן מסתיימת רמה אחת בחיפוש לרוחב?
קרא את גודל התור בתחילת כל סבב. באותו רגע התור מכיל בדיוק את הצמתים של רמה אחת, ולכן הוצאה של מספר כזה של צמתים מוציאה את הרמה ולא יותר. שתי דרכים נוספות עובדות גם הן: לשמור את הרמה הנוכחית ואת הרמה הבאה בשתי רשימות נפרדות, או להוסיף סמן אחרי כל רמה.
האם אפשר לבצע מעבר לפי רמות באמצעות חיפוש לעומק?
כן. העבירו לכל צומת את העומק שלו והוסיפו את הערך שלו לרשימה של אותו עומק. כל עוד המעבר מבקר בתת-העץ השמאלי לפני הימני, כל רשימה תסתיים בסדר משמאל לימין. גם הסיבוכיות היא O(n); חיפוש לרוחב מתאים יותר באופן ישיר, כי הוא מפיק את הרמות לפי הסדר.
המערך כבר מאוחסן לפי רמות. למה לא לקרוא אותו בפרוסות?
בפורמט הזה, שעובד, הרמה d תופסת את האינדקסים 2^d-1 עד 2^(d+1)-2, כך שאפשר לאסוף את הערכים שאינם ריקים בכל טווח ולעצור בטווח הראשון שאין בו ערכים. עם זאת, בריאיון, העץ בדרך כלל מגיע כאובייקטים של צמתים עם מצביעים שמאלה וימינה, וללא אינדקסים שאפשר לחתוך לפיהם. המעבר המבוסס על תור הוא השיטה שמתאימה גם לצורה הזאת וגם לגרסאות כמו סדר זיגזג או מבט מהצד הימני.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def levelOrder(tree):
# כתבו כאן קודמקרה 1
מקרה 2
מקרה 3
קלט
tree = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]
צפוי
[[4], [9, 2], [6, 8, 5], [3]]