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 צמתים.
שאלת המשך
איך תחזיר את הערכים שבמסלול הארוך ביותר מהשורש לעלה, וכן את אורכו? אם יש כמה מסלולים באורך זהה, איזה מהם תחזיר?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
חשוב על השורש. אם היית יודע מהו העומק של תת־העץ השמאלי שלו ומהו העומק של תת־העץ הימני שלו, מה היה העומק של העץ כולו?
העומק הוא
1עבור השורש ועוד העומק הגדול מבין שני תתי־העצים, ולמקום ריק יש עומק0. אותו כלל חל בכל צומת, ולכן מעבר שיודע מה עומקו של כל צומת יכול למצוא את התשובה.שמרו מחסנית של זוגות: אינדקס של צומת והעומק שלו, החל מהשורש בעומק 1. שלפו זוג, זכרו את העומק הגדול ביותר שנראה, ודחפו כל ילד באינדקסים
2*i+1ו-2*i+2שנמצאים בתוך המערך ואינם-1, עם עומק גדול באחד.
פתרון
העומק נקבע לפי הענף הארוך ביותר, ואי אפשר לדעת איזה ענף הוא הארוך ביותר בלי לבקר בכל צומת. לכן צריך מעבר מלא אחד שעוקב אחר העומק בכל צומת. רקורסיה, חיפוש לרוחב לפי רמות וחיפוש לעומק עם מחסנית משלך — כל אחד מהם עושה זאת במעבר אחד.
רקורסיה בשתי תת-העצים
האינטואיציה
מקום של צאצא הוא אמיתי כאשר האינדקס שלו נמצא בתוך המערך והערך שלו אינו -1. המסלול העמוק ביותר דרך צומת יורד אל תת-העץ העמוק יותר שלו, ולכן העומק באינדקס i הוא 1 עבור הצומת ועוד הגדול מבין העומקים באינדקסים 2*i+1 ו-2*i+2. עומקו של מקום ריק הוא 0, וזה מסיים את הרקורסיה. עלה מקבל 1 + max(0, 0) = 1, והערכים מטפסים בחזרה אל השורש.
מבקרים בכל צומת פעם אחת. מחסנית הקריאות מחזיקה מסגרת אחת לכל רמה במסלול הנוכחי, O(h), לכל היותר 14 במקרה הזה.
אלגוריתם
- כתבו
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(w) עבור הרמה הרחבה ביותר. בעץ מלא בעומק 14 מדובר ב-8192 מתוך 16383 הצמתים.
אלגוריתם
- הכניסו את אינדקס השורש
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. כל צומת נדחף פעם אחת, יחד עם אורך הנתיב שמגיע אליו, ולכן העומק הגדול ביותר שאתה מוציא מהמחסנית הוא התשובה. בדוגמה הראשונה, 6 נדחף בתור (9, 4).
המחסנית מחזיקה בערך אח אחד שממתין בכל רמה, 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
מלכודות ומקרי קצה
- ספירת הקשתות במקום הצמתים. ל-
[7, -1, -1]יש עומק1, לא0. - דילוג על בדיקת הגבולות. בדוגמה הראשונה, ל-
6באינדקס 9 יש אינדקסי ילדים 19 ו-20, שחורגים מסוף המערך. יש לבדוקchild < nלפני קריאתtree[child]. - חישוב העומק לפי אורך המערך. ערכי
-1בסוף מגיעים לרמה שאין בה צומת: האורך של[7, -1, -1]הוא 3, אבל העומק הוא 1. - קריאת גודל התור בתוך לולאת האצווה. ילדים שנוספים במהלך האצווה משנים אותו, לכן יש לשמור אותו קודם.
- בלבול בהיסט ב-Lua וב-R, שבהן המערכים מתחילים ב-1. יש להשאיר את אינדקסי הצמתים מבוססי-0 עבור
2*i+1ולקרוא אתtree[i + 1].
שאלות נפוצות3
מהי סיבוכיות הזמן של העומק המרבי של עץ בינארי?
כל אחת מהגישות מבקרת בכל צומת פעם אחת, לכן זמן הריצה הוא O(n). הגרסאות של חיפוש לעומק משתמשות ב־O(h) מקום נוסף עבור המסלול הנוכחי, כאשר h הוא העומק. הגרסה של חיפוש לרוחב משתמשת ב־O(w) עבור הרמה הרחבה ביותר, שבה נמצאים כמחצית מהצמתים בעץ מלא.
האם כדאי להשתמש ב-DFS או ב-BFS כדי למצוא את העומק המרבי של עץ בינארי?
לשניהם זמן ריצה של O(n). קצר יותר לכתוב חיפוש לעומק, והוא משתמש בזיכרון ביחס לעומק, ולכן הוא מתאים לעצים רחבים ורדודים. חיפוש לרוחב סופר ישירות את הרמות ומשתמש בזיכרון ביחס לרמה הרחבה ביותר, ולכן הוא מתאים לעצים עמוקים וצרים. כשמחפשים את העומק המזערי, BFS עדיף כי הוא יכול לעצור בעלה הראשון.
מה ההבדל בין העומק לגובה של עץ בינארי?
העומק של צומת סופר את מספר הצעדים מהשורש ועד אליו; הגובה סופר את מספר הצעדים ממנו ועד לעלה העמוק ביותר שלו. העומק המרבי של העץ שווה לגובה השורש. הבעיה הזו סופרת צמתים, ולכן לצומת יחיד יש עומק 1; ספירת הקשתות נותנת תוצאה קטנה באחד.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def maxDepth(tree):
# כתבו כאן קודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנט
tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
הפלט הצפוי
4