2023 年「資訊科技產業專案設計」作業 1

# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1 > 貢獻者: 馬邦德-lalaman > video: [1](https://youtu.be/dLgekAQhQF4)、[2]()、[3](https://youtu.be/C2GzoD3qUls) > 😇：interviewer > 😊：interviewee ## [94. Binary Tree Inorder Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal/) 😇：假設你正在開發一個簡單的計算機，可以讀取數學運算式並返回計算結果。使用者可以輸入包含加法、減法、乘法和除法的運算式，例如輸入 ```3 + (4 * 2) - 6```會得到```5```。 😇：如果用字串的方式儲存運算式的話會非常麻煩，除了可能會浪費記憶體之外還無法保證能符合「先乘除後加減」等運算規則，你有其他想法嗎？ 😊：所以我要想辦法用最少的記憶體儲存運算式並且要確保運算式能符合運算規則？ 😇:是的 😊：那我打算將使用者輸入的數學運算式解析成一個二元樹，以父節點表示運算符號```+ - / *```並以子節點表示被運算的數字，舉例來說```3 + (4 * 2) - 6```表示成二元樹如下圖 ``` - / \ + 6 / \ * 3 / \ 4 2 ``` 😊：我將使用中序遍歷這個運算式樹。在遍歷過程中，每當我到達一個儲存運算符的節點時，我將執行相對應的計算操作，將左子樹的值和右子樹的值與運算符結合起來，得到一個部分結果，如此下去便可以得到正確的答案。 😇:聽起來不錯，可以請你實做「中序遍歷」的部分嗎？ 😊：沒問題 ### 1.inorder traversal ```c /** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ /** * Note: The returned array must be malloced, assume caller calls free(). */ int* inorderTraversal(struct TreeNode* root, int* returnSize){ int *ans =NULL;//新增一個陣列來儲存答案 int size =0;//由於不知道二元樹的大小，所以用變數size來方便後續記憶體配置 void inorder(struct TreeNode* root)//建立遞迴函式 { if(root) { inorder(root->left);//以遞迴的方式處理左子樹 ans=(int*)realloc(ans,(sizeof(int)*(++size)));//新增陣列的空間 ans[size-1]=root->val;//將根節點的數值放入陣列ans中 inorder(root->right);//以遞迴的方式處理右子數 } } inorder(root);//互叫遞迴函式inorder *returnSize=size;//回傳陣列大小以便後續記憶體釋放 return ans;//將陣列ans回傳 } ``` ### 2.inorder traversal 使用疊代 😇：你的函式執行需要較多次數的函式呼叫，如果呼叫層數比較深，需要增加額外的堆疊處理，還有可能出現堆疊溢位的情況，會對執行效率有一定影響，你有解決辦法嗎？ 😊：確實，當遞迴太深的時候可能就會造成記憶體的問題。我想使用迭代的方式解決這題，並使用堆疊來模擬遞迴，這樣比較好監測與預防堆疊溢位的狀況。 😇：那就麻煩你演示一下「堆疊來模擬遞迴」的部分 😊：沒問題 ```c /** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ /** * Note: The returned array must be malloced, assume caller calls free(). */ // we need stack int top=-1;//初始化stack struct TreeNode** stack=NULL;//建立stack int *ans =NULL;//新增一個陣列來儲存答案 int size =0;//由於不知道二元樹的大小，所以用變數size來方便後續記憶體配置 void push(struct TreeNode* root)//將一個項目加入到堆疊中 { stack=(struct TreeNode**)realloc(stack,(sizeof(struct TreeNode* )*(top+2))); stack[++top]=root; } struct TreeNode* pop()//從堆疊中刪除元素 { if(top==-1) return NULL; return stack[top--]; } void interInorder(struct TreeNode* root) { while(1) { for(;root;root=root->left){//將當前root以及其左子孫們加入堆疊 push(root); } root=pop();//取出堆疊中最上層的節點 if(!root)break;//如果節點不存在便跳出while loop ans=(int*)realloc(ans,(sizeof(int)*(++size)));//新增陣列的空間 ans[size-1]=root->val;//將根節點的數值放入陣列ans中 root=root->right;//將跟變數root更新為原節點的右子樹 } } int* inorderTraversal(struct TreeNode* root, int* returnSize){ ans =NULL;//初始化 size =0;//初始化 interInorder(root);//呼叫疊代函式 *returnSize=size;//回傳陣列大小 return ans;//回傳答案 } ``` ## [701. Insert into a Binary Search Tree](https://leetcode.com/problems/insert-into-a-binary-search-tree/?envType=list&envId=rswxsja3) 😇：不錯，但為了讓使用者操作起來更方便，我們希望計算機能擁有「修改」的功能，例如說```3 + (4 * 2) - 6```可以直接修改成```3 + (4 * 2) - 6+12```不需要重新輸入，你有想法嗎？ 😊:我想給予運算符號假想的數值，再利用二元搜尋樹的特性： *若任意節點的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值；若任意節點的右子樹不空，則右子樹上所有節點的值均大於它的根節點的值；* 來確保計算過程能維持「先乘除後加減」等運算規則並且避免數字與數字之間缺乏運算符號造成錯誤。 😊：所以我會加設原本的數學運算式已經被存在一個二元搜尋樹中，我只需要照規則將數字或運算符號插入即可。 😇：有料，請開始你的表演 ```c /** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ struct TreeNode* insertIntoBST(struct TreeNode* root, int val) { // 基礎情況：當到達一個空節點時，創建一個新節點並返回。 if (root == NULL) { struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode)); newNode->val = val; newNode->left = NULL; newNode->right = NULL; return newNode; } // 如果插入的值小於當前節點的值，則在左子樹中插入。 if (val < root->val) { root->left = insertIntoBST(root->left, val); } // 如果插入的值大於當前節點的值，則在右子樹中插入。 if (val > root->val) { root->right = insertIntoBST(root->right, val); } /*這個遞迴函式的概念類似於 * root * / \ * (被插入的左子樹) (右子數) * * 或者是 * * root * / \ * (左子樹) (被插入的右子數) * * * * */ return root;//將根節點回傳 } ``` 😇:不錯呦，不過為何你要使用遞迴的方式解呢？ 😊：雖然兩者在時間複雜度上是相同的（O(h)，其中h 是樹的高度），但因為BST 本身就是一個遞迴結構（每個子樹都是一個較小的 BST），所以對我而言遞迴解較為直觀。不過若在記憶體空間上有所考量（遞迴方法會使用更多的堆疊空間），迭代也不失為一個好方法。 😇：了解，感謝你今天的參與。 ## 104. Maximum Depth of Binary Tree Interviewer: Good afternoon! How are you today? Interviewee: I'm doing well, thank you! How about you? Interviewer: Great, thanks for asking. Let's jump right into the technical question, shall we? Do you have any experience with binary trees? Interviewee: Yes, I've worked with binary trees in some of my past projects. Interviewer: Great! Then, you should find this question quite interesting. Imagine you're working on a software project that needs to analyze a tree-based data structure. Your task is to write a function in C that calculates the maximum depth of a binary tree. The depth of a tree is the length of the longest path from the root to a leaf. For example, a tree with a single node has a depth of 1. Here's the struct definition for a binary tree node(I will show it in the doc): ```c struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }; ``` Can you write a C function to find the maximum depth of such a binary tree? Interviewee: Sure! I can write a recursive function that traverses the tree and computes the maximum depth. Would you like me to explain my approach before coding it? Interviewer: That sounds like a good plan. Please go ahead. Interviewee: The idea is to recursively explore the left and right subtrees of a given node, calculating their depths. The depth of the current node would then be the maximum of the depths of its left and right subtrees plus 1. If we reach a null node, we return 0 as its depth. Interviewer: Excellent! Please proceed to write the code. Interviewee: Here's the C code for finding the maximum depth of a binary tree. ```c #define max(a, b) ((a) > (b) ? (a) : (b)) int maxDepth(struct TreeNode* root) { if (root == NULL) { return 0; } int leftDepth = maxDepth(root->left); int rightDepth = maxDepth(root->right); return max(leftDepth, rightDepth) + 1; } ``` Interviewer: The code looks great, and your explanation is clear. Do you see any potential issues with this approach? Interviewee: Since this is a recursive approach, it could result in a stack overflow for extremely large trees. However, for most practical cases, this should work just fine. Interviewer: Excellent! You've addressed the problem well. Thank you for your time today. Interviewee: Thank you! It was a pleasure discussing this problem with you. --- ## 第二次作業 - 他評 01 ### Interviewer - [ ] 優點 * 說話清晰，語速正常 * [03:52](https://youtu.be/C2GzoD3qUls?si=t0DSmr-fpzbi2DQG&t=232): 有針對程式本身使用遞迴去進行進一步討論 - [ ] 可改進的地方 * 當interviewee撰寫完後，可以請對方test程式碼的正確性 * [03:52](https://youtu.be/C2GzoD3qUls?si=t0DSmr-fpzbi2DQG&t=232): 詢問完對方遞迴的issue，對方也提出**已知問題**。應該可以再請對方延伸一下這題 * [00:50](https://youtu.be/C2GzoD3qUls?si=n2N1SXzkt_Gtqp9g&t=51): 針對這題可以多給一些example input output，會讓對方更清楚題意。例如:兩邊不同高度的tree，分別是2、3，應該output 3 類似這樣 ### Interviewee - [ ] 優點 * 說話清晰，語速正常 - [ ] 可改進的地方 * 打code時，可以適當的空格不要都黏在一起，看起來會比較清晰 * 缺少了Test的部分，沒有去說服為什麼這麼寫會正確 * 缺少了Optimize的部分，應該嘗試看看非遞迴的寫法 * 缺少了Repeat的部分，這樣如果遇到誤解題目的時候，後面寫Code的部分也會寫錯，會讓面試分數大打折扣。 ## 第二次作業 - 他評 02 ### Interviewer - [ ] 優點 * 有動畫先給個讚，不愧是驚喜阿！ * 講話清楚 - [ ] 可改進的地方 * 可以想一個故事來包裝題目 ### Interviewee - [ ] 優點 * 講話清楚語速剛好，讓人可以很好的理解你的步驟 * 程式碼有註解超棒 - [ ] 可改進的地方 * 影片中的code要記得排版，不只讓人舒服，更是讓interviewer可以瀏覽的更清楚與快速，推薦的排版方式，請看一下該[網站](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-a#clang-format-%E5%B7%A5%E5%85%B7%E5%92%8C%E4%B8%80%E8%87%B4%E7%9A%84%E7%A8%8B%E5%BC%8F%E6%92%B0%E5%AF%AB%E9%A2%A8%E6%A0%BC) ## 第二次作業 - 他評 03 ### Interviewer - [ ] 優點 * 題目有經過包裝，舉出實例應用，更貼近實際面試 ### Interviewee - [ ] 優點 * 口齒清晰 - [ ] 可改進的地方 * 可以先重複一次題目的要求確保理解題目(實際面試不一定一次就聽懂題目或馬上想到解決方法，重複題目也給自己時間緩衝做思考)