Maximum Depth of Binary Tree
ניתן לך עץ בינארי המאוחסן במערך tree בסדר לפי רמות. השורש נמצא באינדקס 0, הילדים של הצומת באינדקס i נמצאים באינדקסים 2*i+1 (שמאל) ו־2*i+2 (ימין), -1 מציין מקום ריק, והמערך עשוי להסתיים בערכי -1 נוספים. החזר את העומק המרבי של העץ: מספר הצמתים במסלול הארוך ביותר מהשורש ועד לעלה.
פונקציה
- treeinteger-array
- העץ הבינארי לפי סדר רמות, כאשר -1 מציין מקום ריק
- מחזירהinteger
- מספר הצמתים במסלול הארוך ביותר מהשורש לעלה
אילוצים
1 ≤ tree.length ≤ 32767- כל
tree[i]הוא-1או ערך שמקיים0 ≤ tree[i] ≤ 1000. tree[0]לעולם אינו-1, לכן יש בעץ לפחות צומת אחד.- המערך עשוי להסתיים בערכי
-1נוספים אחרי הצומת האחרון. - גם שני הילדים של מקום ריק ריקים, והעומק הוא לכל היותר
14.
דוגמאות
- קלט
- tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
- פלט
- 4
- הסבר
- המסלול הארוך ביותר הוא
5,8,3,6(האינדקסים0,1,4,9), והוא מכיל 4 צמתים. המסלול דרך1נעצר אחרי 2 צמתים.
- קלט
- tree = [7, -1, -1]
- פלט
- 1
- הסבר
- שתי הרשומות
-1הן המקומות הריקים של הילדים של השורש. השורש לבדו הוא מסלול של צומת אחד, ולכן העומק הוא1, ולא0.
- קלט
- tree = [2, -1, 9, -1, -1, -1, 4]
- פלט
- 3
- הסבר
- לשורש
2אין צומת בן שמאלי. לצומת הבן הימני שלו9באינדקס2יש את4באינדקס6כצומת בן ימני, מסלול של 3 צמתים.
+13 בדיקות נסתרות בשליחה
שאלת המשך
איך היית מחזיר את הערכים שבנתיב הארוך ביותר מהשורש לעלה, ולא רק את אורכו? אם כמה נתיבים שווים באורכם, איזה מהם היית מחזיר, ואיך היית מציין זאת בחוזה?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
חשוב על השורש. אם היית יודע את העומק של תת-העץ השמאלי שלו ואת העומק של תת-העץ הימני שלו, מה היה העומק של העץ כולו?
זה
1עבור השורש ועוד העומק הגדול מבין שני תתי־העצים, ולמקום ריק יש עומק0. אותו כלל חל בכל צומת, ולכן מעבר שיודע מה עומקו של כל צומת יכול למצוא את התשובה.החזק מחסנית של זוגות: אינדקס של צומת והעומק שלו, החל מהשורש בעומק 1. הוצא זוג מהמחסנית, זכור את העומק הגדול ביותר שנראה עד כה, ודחוף כל ילד באינדקס
2*i+1ובאינדקס2*i+2אם הוא נמצא בתוך המערך ואינו-1, עם עומק גדול באחד.
פתרון
העומק נקבע לפי הענף הארוך ביותר, ואי אפשר לדעת איזה ענף הוא הארוך ביותר בלי לבדוק כל צומת. לכן, המשימה היא סריקה מלאה שיודעת מה העומק בכל צומת. רקורסיה, חיפוש לרוחב רמה אחר רמה וחיפוש לעומק באמצעות מחסנית משלך — כולם מבצעים זאת במעבר אחד; הם נבדלים באופן שבו הם עוקבים אחר המיקום שלהם.
רקורסיה בשני תתי-העצים
האינטואיציה
ראשית, איך נעים במערך. לצומת באינדקס i יש בן שמאלי באינדקס 2*i+1 ובן ימני באינדקס 2*i+2. בן קיים רק אם האינדקס שלו נמצא בתוך המערך והערך שם אינו -1. במערך [5, 8, 1, -1, 3, -1, -1, -1, -1, 6], לשורש 5 יש ילדים באינדקסים 1 ו-2; לצומת 8 באינדקס 1 יש מקום ריק משמאל באינדקס 3 והצומת 3 באינדקס 4 מימינו, ומתחת לצומת 3 נמצא הצומת 6 באינדקס 9.
ועכשיו לרעיון. המסלול העמוק ביותר דרך צומת ממשיך מטה אל תת-העץ העמוק יותר מבין שני תתי-העצים שלו. לכן עומק תת-העץ באינדקס i הוא 1 עבור הצומת עצמו, ועוד הגדול מבין העומקים באינדקסים 2*i+1 ו-2*i+2. למקום ריק יש עומק 0, וזה מסיים את הרקורסיה. עלה מקבל 1 + max(0, 0) = 1, והערכים מטפסים בחזרה אל השורש.
מבקרים בכל צומת פעם אחת, לכן זמן הריצה הוא O(n). מחסנית הקריאות מחזיקה מסגרת אחת לכל רמה במסלול הנוכחי, O(h), כאשר h הוא העומק, ולכל היותר 14 כאן. המגבלה הזאת היא מה שהופך את הרקורסיה לבטוחה בבעיה הזאת. בעץ המבוסס על מצביעים, שצורתו כמו שרשרת ארוכה, אותו קוד היה מגיע למגבלת הרקורסיה, שהיא 1000 מסגרות ב-Python.
אלגוריתם
- כתבו
depth(i): אםiנמצא מעבר לסוף המערך אוtree[i]הוא-1, החזירו0. - אחרת, החזירו
1 + max(depth(2*i+1), depth(2*i+2)). - החזירו
depth(0).
def maxDepth(tree):
def depth(i):
# An index past the end or a -1 is an empty spot: depth 0.
if i >= len(tree) or tree[i] == -1:
return 0
return 1 + max(depth(2 * i + 1), depth(2 * i + 2))
return depth(0)חיפוש לרוחב, רמה אחר רמה
האינטואיציה
העומק המרבי הוא מספר הרמות בעץ, ולכן אפשר לספור רמות במקום לעקוב אחר מסלולים. תור מבקר בצמתים לפי סדר הרמות: מתחילים אותו עם השורש, ובכל פעם שמוציאים ממנו צומת, מוסיפים את הילדים הקיימים שלו לסוף.
כדי לספור רמות, מעבדים את התור בקבוצות. לפני כל קבוצה, בודקים כמה צמתים יש בתור. אלה בדיוק הצמתים של רמה אחת, כי הילדים שמוסיפים במהלך הקבוצה נכנסים מאחוריהם. מוציאים את מספר הצמתים הזה, מכניסים את הילדים שלהם לתור ומוסיפים 1 לעומק. כשהתור ריק, העומק הוא מספר הקבוצות. בדוגמה הראשונה הקבוצות הן [5], [8, 1], [3] ו־[6], ולכן התשובה היא 4.
כל צומת נכנס לתור ויוצא ממנו פעם אחת, זמן O(n). התור מכיל בכל פעם רמה אחת, ונדרש מקום O(w) עבור הרמה הרחבה ביותר w. בעץ מלא, הרמה התחתונה מכילה כמחצית מהצמתים: 8192 מתוך 16383 בעומק 14.
אלגוריתם
- הכניסו את אינדקס השורש
0לתור והגדירוdepth = 0. - כל עוד התור אינו ריק, הוסיפו
1ל־depthוקראו את גודל התור. - הוציאו את אותו מספר של אינדקסים. עבור כל אחד מהם, הכניסו לתור את אינדקסי הילדים
2*i+1ו־2*i+2שנמצאים בתוך המערך ואינם-1. - כשהתור ריק, החזירו את
depth.
from collections import deque
def maxDepth(tree):
n = len(tree)
queue = deque([0])
depth = 0
while queue:
depth += 1
for _ in range(len(queue)): # exactly the nodes of this level
i = queue.popleft()
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
queue.append(child)
return depthחיפוש לעומק תחילה באמצעות מחסנית מפורשת
האינטואיציה
אפשר לעבור לאורך מסלולים, כפי שעושה הרקורסיה, בלי לבצע אפילו קריאה רקורסיבית אחת. שמרו מחסנית משלכם, ואחסנו כל צומת יחד עם העומק שלו, כי שום דבר אחר לא זוכר כמה עמוק הוא נמצא. התחילו בזוג (0, 1): השורש, בעומק 1.
הוציאו זוג מהמחסנית, השוו את העומק שלו לעומק המרבי שנראה עד כה, ודחפו כל ילד ממשי עם depth + 1. כל צומת בעץ נדחף בדיוק פעם אחת, יחד עם אורך המסלול שמגיע אליו, ולכן העומק המרבי של זוג שאתם מוציאים הוא התשובה. בדוגמה הראשונה, ה-6 באינדקס 9 נדחף בתור (9, 4), ואף זוג לא מגיע לעומק רב יותר.
זמן הריצה הוא O(n). המחסנית מכילה את האחים הממתינים לאורך המסלול הנוכחי, לכל היותר בערך אחד לכל רמה, ולכן המקום הוא O(h), כמו ברקורסיה, אך בלי מחסנית קריאות שעלולה לגלוש. זו הגרסה שכדאי לבחור בה כשהעץ עשוי להיות עמוק, והיא עוברת ללא שינוי גם לעצים המבוססים על מצביעים.
אלגוריתם
- דחוף את
(0, 1)למחסנית והגדרbest = 0. - שלוף זוג
(i, depth)והגדר אתbestכגדול מביןbestו-depth. - עבור כל אינדקס של ילד,
2*i+1ו-2*i+2, שנמצא בתוך המערך ואינו-1, דחוף אותו עםdepth + 1. - חזור על הפעולה עד שהמחסנית ריקה, ואז החזר את
best.
def maxDepth(tree):
n = len(tree)
best = 0
stack = [(0, 1)] # (node index, depth of that node); the root is never empty
while stack:
i, depth = stack.pop()
best = max(best, depth)
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
stack.append((child, depth + 1))
return best
מלכודות ומקרי קצה
רוב התשובות השגויות לבעיה הזו הן בהפרש של אחד, או נובעות מהתייחסות למקום ריק כאל צומת.
- סופרים קשתות במקום צמתים. לעץ עם צומת יחיד יש כאן עומק
1; החזרת0עבורו, או3עבור מסלול של 4 צמתים, קצרה באחד. - מדלגים על בדיקת הגבולות. לעלה שקרוב לסוף המערך יכולים להיות אינדקסים של ילדים שחורגים מהאיבר האחרון בו, כי ייתכן שהמערך מסתיים מיד אחרי הצומת האחרון. בדקו
child < nלפני קריאתtree[child]. - מסיקים את העומק מאורך המערך. ייתכן שבמערך יש ערכי
-1נוספים בסוף, ולכן אורכו עשוי להתאים לרמה עמוקה יותר מכל צומת אמיתי. - מתייחסים ל-
-1כאל ערך. הוא מסמן צומת חסר, ולכן אסור להוסיף אותו למחסנית או לתור, או לספור אותו. - מניחים שהעץ מאוזן. התשובה נקבעת לפי הענף הארוך ביותר, כמו בשרשרת שמאלית של 14 צמתים שבה כל המקומות הימניים ריקים.
- קוראים את גודל התור בתוך הלולאה בגרסה שמשתמשת בחיפוש לרוחב. הגודל משתנה כשמוסיפים ילדים, לכן שמרו אותו לפני תחילת האצווה.
- מתבלבלים בהיסט ב-Lua וב-R, שבהן מערכים מתחילים ב-1. השאירו את אינדקסי הצמתים מבוססי 0 עבור חישוב
2*i+1, וקראו אתtree[i + 1].
שאלות נפוצות4
מהי סיבוכיות הזמן של העומק המרבי של עץ בינארי?
כל גישה מבקרת בכל צומת פעם אחת, ולכן זמן הריצה הוא O(n). הגרסאות של חיפוש לעומק משתמשות בזיכרון נוסף של O(h) עבור הנתיב שנבדק, כאשר h הוא העומק. הגרסה של חיפוש לרוחב משתמשת ב-O(w) עבור הרמה הרחבה ביותר, שיכולה להכיל כמחצית מהצמתים בעץ מלא.
האם כדאי להשתמש ב-DFS או ב-BFS כדי למצוא את העומק המרבי של עץ בינארי?
שתיהן נותנות את התשובה הנכונה בזמן O(n). חיפוש לעומק קצר יותר לכתיבה וצורך זיכרון ביחס לעומק, ולכן מתאים לעצים רחבים ורדודים. חיפוש לרוחב סופר את הרמות ישירות וצורך זיכרון ביחס לרמה הרחבה ביותר, ולכן מתאים לעצים עמוקים וצרים. למציאת העומק המינימלי, ל-BFS יש יתרון, כי הוא יכול לעצור בעלה הראשון שהוא פוגש.
איך מוצאים את העומק המרבי של עץ בינארי ללא רקורסיה?
השתמשו במחסנית מפורשת של זוגות: צומת והעומק שלו. התחילו עם השורש בעומק 1, הוציאו זוג מהמחסנית, תעדו את העומק שלו והכניסו למחסנית כל ילד עם עומק גדול באחד. העומק הגדול ביותר שתוציאו מהמחסנית הוא התשובה. גם תור שמעבדים רמה אחת בכל פעם עובד, כשסופרים אחד לכל רמה.
מה ההבדל בין העומק לגובה של עץ בינארי?
העומק של צומת הוא מספר הצעדים מהשורש ועד אליו, והגובה של צומת הוא מספר הצעדים ממנו ועד לעלה העמוק ביותר שלו. העומק המרבי של העץ והגובה של השורש הם אותו מספר. הבעיה הזו סופרת צמתים, ולכן לצומת יחיד יש עומק 1; יש ספרים שסופרים במקום זאת קשתות, מה שמניב מספר קטן באחד.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def maxDepth(tree):
# כתבו כאן את הקודמקרה 1
מקרה 2
מקרה 3
קלט
tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
צפוי
4