שאלת מבחן במבוא למדעי המחשב - אוניברסיטת בר-אילן 2024 - רקורסיה

**הגדרה:** מסלול בעץ בינארי הינו רצף מחובר של קודקודים. מסלול לא חייב להתחיל בשורש, ולא חייב להסתיים בעלה. מסלול יכול להכיל קודקוד יחיד. ממשו פונקציה **רקורסיבית** findAllPaths אשר מקבלת עץ בינארי T ומספר שלם x ומחזירה את מספר המסלולים ב-T אשר סכום ערכי הקודקודים במסלולים האילו הינו x. דוגמה: בהנתן העץ הבא ו-$x = 7$: ``` 1 / \ 2 -2 / \ / \ -1 5 8 4 | | 7 5 ``` ישנם ארבעה מסלולים בעץ אשר סכום הערכים של הקודקודים בהם הינו 7 (המסלולים מסומנים בחצים, ומסלול אחד שמכיל קודקוד יחיד עם ערך 7 מסומן בעיגול). ```c typedef struct TNode { int val; struct TNode *left; struct TNode *right; } TNode; int findAllPaths(TNode *T, int x); ``` **שימו לב:** פתרון שאינו רקורסיבי לא יזכה אותכם בניקוד.

רמז: פתרו בשני שלבים: (1) פונקציית עזר שסופרת מסלולים **המתחילים** מצומת נתון ויורדים למטה עם סכום x. (2) הפונקציה הראשית קוראת לעזר מכל צומת בעץ (כך שכל צומת יכול להיות תחילת מסלול).

פתרון: ```c // Helper: counts paths starting from node going downward with remaining sum int countFromNode(TNode *node, int remaining) { if (!node) return 0; int count = (remaining == node->val) ? 1 : 0; count += countFromNode(node->left, remaining - node->val); count += countFromNode(node->right, remaining - node->val); return count; } int findAllPaths(TNode *T, int x) { if (!T) return 0; // Count paths starting from T int count = countFromNode(T, x); // Also count paths in left and right subtrees (not starting from T) count += findAllPaths(T->left, x); count += findAllPaths(T->right, x); return count; } ``` **הסבר:** שתי פונקציות רקורסיביות: 1. **countFromNode(node, remaining):** סופרת מסלולים שמתחילים **בדיוק מ-node** ויורדים למטה. אם `node->val == remaining`, מצאנו מסלול. ממשיכים רקורסיבית שמאלה וימינה עם `remaining - node->val`. 2. **findAllPaths(T, x):** לכל צומת בעץ, קוראת ל-countFromNode (כדי לבדוק מסלולים שמתחילים ממנו), ואז קוראת רקורסיבית על תת-העצים. **אימות על הדוגמה** ($x = 7$): 4 מסלולים: - $2 \to 5$ - $-2 \to 4 \to 5$ - $7$ (קודקוד בודד) - $1 \to 2 \to -1 \to 5$ (... or another combination) $\blacksquare$