Diameter 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 = [8, 3, 6, 1, 4, -1, -1, -1, -1, 7]
- פלט
- 4
- הסבר
- המסלול
7,4,3,8,6(אינדקסים9,4,1,0,2) מכיל חמישה צמתים המחוברים באמצעות ארבע קשתות. הוא פונה בשורש: שלוש קשתות יורדות בצד שמאל ואחת יורדת בצד ימין.
- קלט
- tree = [2, 5, -1, 1, 9, -1, -1, 3, -1, -1, 4]
- פלט
- 4
- הסבר
- במסלול
3,1,5,9,4יש ארבע צלעות, והוא פונה ב־5באינדקס1. לשורש אין בן ימני, לכן מסלול דרך השורש כולל רק את שלוש הצלעות שיורדות בצד שמאל שלו.
- קלט
- tree = [6, -1, -1]
- פלט
- 0
- הסבר
- לצומת יחיד אין קשתות. המסלול הארוך ביותר הוא הצומת עצמו, באורך
0.
שאלת המשך
איך תחזיר את הנתיב עצמו, את ערכי הצמתים מקצה אחד של הקוטר לקצה השני?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
לכל מסלול בעץ יש צומת אחד שהוא הגבוה ביותר, שבו המסלול עובר מעלייה לירידה. אם היית יודע מהו הצומת הזה, מה יכול להיות אורכו של המסלול שעובר דרכו?
מסלול שפונה בצומת
iיורד לתת־העץ השמאלי ויורד לתת־העץ הימני. לכל היותר אורכו הוא גובהו של הבן השמאלי ועוד גובהו של הבן הימני, כאשר גובה הוא מספר הצמתים במסלול היורד הארוך ביותר, ולמקום ריק יש גובה0.חשבו את הגבהים מלמטה למעלה במעבר אחד בסדר פוסט־סדר: הגובה של צומת הוא
1 + max(left, right). בזמן שמחזיקים אתleftואתrightבצומת, עדכנו את התשובה בעזרתleft + right.
פתרון
המסלול הארוך ביותר לא חייב לעבור דרך השורש, ולכן מדידת שני הצדדים של השורש אינה מספיקה. לכל מסלול יש צומת אחד שנמצא בנקודה הגבוהה ביותר שלו, שבה הוא פונה מעלייה לירידה, והמסלול הארוך ביותר שפונה בצומת הוא גובה תת-העץ השמאלי שלו ועוד גובה תת-העץ הימני שלו. מעבר אחד בסדר שלאחר הסדר מחשב את הגובה של כל צומת מלמטה למעלה ובודק כל נקודת פנייה בדרך, בזמן O(n).
מדוד כל זוג צמתים
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
ראשית, כיצד לנוע במערך. לצומת באינדקס i יש בן שמאלי באינדקס 2*i+1 ובן ימני באינדקס 2*i+2, ולכן ההורה שלו נמצא באינדקס (i-1)/2, בעיגול כלפי מטה. מיקום קיים רק אם האינדקס שלו נמצא בתוך המערך והערך בו אינו -1. ב־[8, 3, 6, 1, 4, -1, -1, -1, -1, 7], ל־7 שבאינדקס 9 יש הורה באינדקס 4, ולהורה הזה, 4, יש הורה באינדקס 1.
הקוטר הוא המרחק הגדול ביותר בין שני צמתים, ולכן אפשר למדוד כל זוג. כדי למצוא את המרחק בין האינדקסים a ו־b, מתקדמים צעד אחד בכל פעם לכיוון השורש עד שנפגשים, ותמיד מתחילים מהאינדקס הגדול יותר. אינדקס גדול יותר לעולם אינו נמצא ברמה גבוהה יותר, ולכן הצעד הזה לעולם אינו עובר את נקודת המפגש. מספר הצעדים הוא מספר הקשתות. עבור 9 ו־2: ה־9 עולה ל־4 ואז ל־1, ה־2 עולה ל־0, וה־1 עולה ל־0. ארבעה צעדים.
זה נכון, אבל איטי. הבדיקה הגדולה ביותר היא עץ מלא עם 16383 צמתים, שמייצר בערך 1.3 × 10^8 זוגות, וכל זוג דורש עד 26 צעדים. מיליארדי צעדים כדי לקבל תשובה אחת הם הרבה מעבר למגבלת הזמן.
אלגוריתם
- אספו את האינדקסים של כל הצמתים האמיתיים.
- עבור כל זוג
(a, b), הגדירוedges = 0וחזרו על הפעולה עד ש-a == b: החליפו את האינדקס הגדול יותר באב שלו והוסיפו1ל-edges. - שמרו את הערך הגדול ביותר של
edgesשנתקלתם בו והחזירו אותו.
def diameterOfBinaryTree(tree):
nodes = [i for i, value in enumerate(tree) if value != -1]
best = 0
for x in range(len(nodes)):
for y in range(x + 1, len(nodes)):
a, b = nodes[x], nodes[y]
edges = 0
while a != b:
# A larger index is never higher up, so climb from it.
if a > b:
a = (a - 1) // 2
else:
b = (b - 1) // 2
edges += 1
best = max(best, edges)
return bestמדוד את שני הגבהים בכל צומת
האינטואיציה
התבוננו במסלול הארוך ביותר מהצומת הגבוה ביותר שלו — הצומת שבו המסלול מפסיק לעלות ומתחיל לרדת. משם הוא יורד ככל האפשר בצד שמאל וככל האפשר בצד ימין. נגדיר את height(c) כמספר הצמתים במסלול היורד הארוך ביותר מ־c, כאשר עבור מקום ריק הערך הוא 0. אז במסלול הארוך ביותר שפונה בצומת i יש height(2*i+1) + height(2*i+2) קשתות — קשת אחת עבור כל אחד מהצמתים האלה.
לכן, נסו כל צומת כנקודת הפנייה ושמרו את התוצאה הטובה ביותר. בדוגמה השנייה, ל־5 שבאינדקס 1 יש גובה 2 בצד שמאל (1, 3) ו־2 בצד ימין (9, 4), כך שהמסלול כולל ארבע קשתות. לשורש יש גובה 3 בצד שמאל ו־0 בצד ימין, ולכן המסלול כולל רק שלוש קשתות.
כל קריאה ל־height עוברת על תת־עץ שלם, וכל צומת נסרק שוב עבור כל אב קדמון שמעליו, ולכן זמן הריצה הוא O(n·h). כאשר h ≤ 14, זה מהיר מספיק כאן, אבל בעץ מצביעים בצורת שרשרת h יכול להגיע ל־n, ואז אותה גישה עולה O(n²). הקריאות החוזרות ל־height הן הבזבוז שהגישה האחרונה מונעת.
אלגוריתם
- כתבו את
height(i):0עבור מקום ריק, אחרת1 + max(height(2*i+1), height(2*i+2)). - עבור כל צומת ממשי
i, חשבו אתheight(2*i+1) + height(2*i+2). - החזירו את הגדול ביותר מבין הסכומים האלה.
def diameterOfBinaryTree(tree):
n = len(tree)
def height(i):
# Nodes on the longest downward path from i; an empty spot has 0.
if i >= n or tree[i] == -1:
return 0
return 1 + max(height(2 * i + 1), height(2 * i + 2))
best = 0
for i in range(n):
if tree[i] != -1:
# The longest path that turns at node i goes down both sides.
best = max(best, height(2 * i + 1) + height(2 * i + 2))
return bestמעבר אחד בסדר post-order על הגבהים
האינטואיציה
הגובה של צומת תלוי רק בגבהים של שני ילדיו, ואלה אותם שני מספרים שבדיקת נקודת המפנה זקוקה להם. לכן מחשבים אותם פעם אחת, מלמטה למעלה. מעבר בסדר post-order מסיים לעבד את שני הילדים לפני ההורה שלהם. בכל צומת יש לך אז את left ואת right: מעדכנים את התשובה באמצעות left + right, ומעבירים להורה את 1 + max(left, right).
בדוגמה הראשונה העלה 7 מחזיר 1, הצומת 4 שמעליו מחזיר 2, והצומת 3 מחזיר 3, משום שלילד השני שלו, 1, יש גובה 1. הצומת 6 מחזיר 1. בשורש, left + right = 3 + 1 = 4, וזוהי התשובה. התוצאה הטובה ביותר שמציע כל צומת אחר היא 3, עם 1 + 2 = 3.
מבקרים בכל צומת פעם אחת, ולכן זמן הריצה הוא O(n), והעומק של הרקורסיה זהה לעומק העץ, O(h), בערך מסגרת אחת לכל רמה. התשובה נשמרת במשתנה מחוץ לרקורסיה, משום שמה שהקריאה מחזירה (גובה) אינו מה שרוצים בסוף (אורך מסלול).
אלגוריתם
- הגדר את
best = 0וכתוב אתheight(i). עבור מקום ריק, החזר0. - חשב את
left = height(2*i+1)ואתright = height(2*i+2). - הגדר את
bestלהיות הגדול מביןbestלביןleft + right. - החזר
1 + max(left, right). - קרא ל-
height(0)והחזר אתbest.
def diameterOfBinaryTree(tree):
n = len(tree)
best = 0
def height(i):
# Returns the height of node i and updates best on the way back up.
nonlocal best
if i >= n or tree[i] == -1:
return 0
left = height(2 * i + 1)
right = height(2 * i + 2)
best = max(best, left + right) # the longest path that turns at node i
return 1 + max(left, right)
height(0)
return best
מלכודות ומקרי קצה
רוב התשובות השגויות סופרות את הדבר הלא נכון או מודדות בצומת הלא נכון.
- סופרים צמתים במקום קשתות. למסלול
7,4,3,8,6יש חמישה צמתים ואורכו4, ולצומת יחיד יש קוטר0. - מודדים רק דרך השורש. בדוגמה השנייה, למסלול הטוב ביותר שעובר דרך השורש יש שלוש קשתות, והתשובה היא ארבע, כשהפנייה מתרחשת באינדקס
1. - מחזירים את הקוטר מהקריאה הרקורסיבית. ההורה זקוק לגבהים של ילדיו כדי לבנות מסלולים ארוכים יותר; הקוטר צריך להישמר במשתנה נפרד.
- מערבבים בין שתי מוסכמות של גובה. כאשר הגבהים סופרים צמתים ומשתמשים ב-
0עבור מקום ריק,left + rightכבר נותן את מספר הקשתות. בגבהים שסופרים קשתות, יש להשתמש ב--1עבור מקום ריק וב-left + right + 2. שימוש בחצי מכל אחת מהמוסכמות יוצר סטייה של אחת או שתיים. - קוראים מעבר לסוף. לעלה סמוך לסוף המערך יכולים להיות אינדקסים של ילדים מעבר לאיבר האחרון בו. יש להתייחס לאינדקס שמעבר לסוף כאל מקום ריק.
- מתבלבלים בהיסט ב-Lua וב-R, שבהן המערכים מתחילים ב-1. יש להשאיר את אינדקסי הצמתים מבוססי 0 לצורך החישוב
2*i+1, ולקרוא אתtree[i + 1].
שאלות נפוצות3
מהי סיבוכיות הזמן של Diameter of Binary Tree?
הפתרון בסדר מעבר שלאחר הסדר מבקר בכל צומת פעם אחת, ולכן זמן הריצה שלו הוא O(n), עם מקום נוסף של O(h) עבור הרקורסיה, כאשר h הוא הגובה. חישוב הגבהים בנפרד בכל צומת עולה O(n·h), ובכך הופך ל־O(n²) בעץ שצורתו שרשרת.
האם הקוטר של עץ בינארי תמיד עובר דרך השורש?
לא. המסלול הארוך ביותר יכול להיות כולו בתוך תת־עץ אחד, למשל כאשר לשורש יש ענף קצר אחד ותת־עץ עמוק ומסועף בצד השני. לכן בודקים את left + right בכל צומת, ולא רק בשורש.
האם הקוטר נספר בצמתים או בקשתות?
כאן סופרים לפי קשתות — הקישורים בין צמתים עוקבים במסלול — ולכן לצומת יחיד יש קוטר של 0, ולשני צמתים מחוברים יש קוטר של 1. בספרים מסוימים סופרים צמתים במקום זאת, ואז התוצאה גדולה באחד. בדקו מה מבקשים בשאלה לפני שמוסיפים או מחסירים את 1.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def diameterOfBinaryTree(tree):
# כתבו כאן את הקודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנט
tree = [8, 3, 6, 1, 4, -1, -1, -1, -1, 7]
הפלט הצפוי
4