## LeetCode 模擬面試練習 >[video](https://youtu.be/0Yjj4ODsC60) ### [701. Insert into a Binary Search Tree](https://leetcode.com/problems/insert-into-a-binary-search-tree/?envType=list&envId=rswxsja3) Interviewer: 早上好，馬先生。感謝您今天的參與。在我們開始之前，請您簡單介紹一下您自己。 Interviewee: 早上好，我是馬邦德，畢業於成功大學資訊工程系，過去在鵝城擔任軟體工程師，專注於後端開發和資料結構的設計。 Interviewer: 太好了。目前公司正在為一個網購平台建立新的商品管理系統。 這個平台有數以萬計的商品，每個商品都有自己的價格和庫存資訊。由於平台非常受歡迎，每天都會有大量的價格更新和庫存變動。我們希望能夠迅速地找到和更新特定的商品資訊。 對於如何優化這個流程。你有什麼想法嗎？ Interviewee: 如果我理解正確的話，我需要設計一個函式，這個函式接收一個新的商品並加入到系統的資料庫中，並能保持原先的結構和排序特性，對吧？ Interviewer: 完全正確。 Interviewee: 那我想使用二元搜尋樹（BST）來儲存商品訊息，以商品的價格作為排序的依據。 而函式要能夠接收一個BST的根節點和一個商品，然後將該商品插入到BST中的正確位置，以保持樹的結構。 Interviewer: 聽起來不錯。 Interviewee: 例如，如果我們有一個二元搜尋樹，根節點是 5，並且我要插入一個值 3，那麼 3 應該會被插入到 5 的左子節點。 Interviewer: 了解。 Interviewee: 我的做法是遞迴。從根節點開始，如果新的值小於當前節點的值，我將向左遞迴；如果新的值大於當前節點的值，我將向右遞迴。當達到一個空節點時，我將在這裡插入新的節點。 ``` c // 定義二元搜尋樹的節點結構 struct TreeNode { int val; // 節點值 struct TreeNode *left; // 左子節點指針 struct TreeNode *right; // 右子節點指針 }; // 函式: 在二元搜尋樹中插入一個新節點 struct TreeNode* insertIntoBST(struct TreeNode* root, int val) { // 如果根節點是空的，創建一個新節點，並將其返回作為新的根節點 if (root == NULL) { struct TreeNode* new_node = malloc(sizeof(struct TreeNode)); new_node->val = val; new_node->left = NULL; new_node->right = NULL; return new_node; } // 如果要插入的值小於根節點的值，遞迴在左子樹中插入 if (val < root->val) { root->left = insertIntoBST(root->left, val); } // 如果要插入的值大於根節點的值，遞迴在右子樹中插入 else if (val > root->val) { root->right = insertIntoBST(root->right, val); } // 返回可能已經更新的根節點 return root; } ``` Interviewee: 讓我來測試一下代碼是否能順利運行 ``` c #include <stdio.h> #include <stdbool.h> #include <limits.h> #include<stdlib.h> // 定義二元樹節點結構 struct treenode { int val; struct treenode* left; struct treenode* right; }; //檢測一個樹是否是BST bool isBSTUtil(struct treenode* node, int min, int max) { if (node == NULL) { return true; // 空樹是BST } if (node->val <= min || node->val >= max) { return false; // 不滿足BST特性 } // 遞歸檢查左子樹和右子樹 return isBSTUtil(node->left, min, node->val) && isBSTUtil(node->right, node->val, max); } struct treenode* insertIntoBST(struct treenode* root, int val) { if (root == NULL) { struct treenode* new_node = malloc(sizeof(struct treenode)); new_node->val = val; new_node->left = NULL; new_node->right = NULL; return new_node; } if (val < root->val) { root->left = insertIntoBST(root->left, val); } else if (val > root->val) { root->right = insertIntoBST(root->right, val); } return root; } int main() { // 構建一個示例二元樹 struct treenode* root = malloc(sizeof(struct treenode)); root->val = 10; root->left = NULL; root->right = NULL; // 插入新節點 root = insertIntoBST(root, 5); root = insertIntoBST(root, 15); root = insertIntoBST(root, 2); root = insertIntoBST(root, 7); root = insertIntoBST(root, 7); // 檢測樹是否是BST if (isBSTUtil(root,INT_MIN, INT_MAX)) { printf("這棵樹是二元搜索樹。\n"); } else { printf("這棵樹不是二元搜索樹。\n"); } return 0; } ``` Interviewer: 你的解決方案很清楚。請問你的這個函式的時間和空間複雜度是什麼？ Interviewee: 在遞迴版本中，時間複雜度是 O(h)，其中 h 是樹的高度。每一個遞迴呼叫都會走訪樹的一個節點，直至找到適當的插入位置。而空間複雜度是主要由於遞迴呼叫堆疊的深度，它也是 O(h)。在平衡的情況下，h 是 log(n)，所以時間和空間複雜度都是 O(log n)；但是，在最壞的情況下，樹可能是非常偏斜的，使得 h 接近 n，因此時間和空間複雜度都是 O(n)。 Interviewer: 非常好。那如果我們想要優化這個函式以達到更好的效能，您會怎麼做？ Interviewee: 我打算避免遞迴並使用迭代來找到新節點應該插入的位置， 在最壞的情況下（樹是完全不平衡的），時間複雜度是 O(n)，其中 n 是樹中的節點數。在最好的情況下（樹是完全平衡的），時間複雜度是O(logn) 而空間複雜度由於避免了遞迴，減少到 O(1)。 這個方法也保留了二元搜尋樹的特性，並能夠正確地插入新節點。 Interviewer: 非常感謝您的回答和努力，馬先生。我們稍後會通知您面試的結果。祝您今天過得愉快！ Interviewee: 謝謝您，期待您的回音。再見！ --- ## 簡介你對其他同學的批評 (正反面都有)，和你從中學到什麼 ## 1.塔塔 Jennifer （補充） > 10:08: 「有沒有其他解法解這個問題?」可以換個方式問，問說有沒有覺得這個解法哪裡可以換做其他解法去嘗試看看。 > 12:23 缺少了Test的部分，沒有去說服為什麼這麼寫會正確 缺少了Optimize的部分 ## 2.優嬉兔-UCI-他評 05 ### interviewer - [ ] 優點 * 口齒清晰 - [ ] 可改進的地方 * 建議不要直接使用leetcode原題，可對題目做適當的包裝 * 對話內容有點太制式 ### interviewee - [ ] 優點 * 在書寫程式碼的過程中有搭配適度的解釋 - [ ] 可改進的地方 * 缺少test的環節 ### 3.半條悟-satoru - 他評06 ### Interviewer - [ ] 優點 * 表達相當清楚 - [ ] 可改進之處 * 若能跟Interviewee有更多互動會更好 ### Interviewee - [ ] 優點 * REATO做的相當完整 * 在書寫程式碼的過程中有搭配很詳細的解釋 - [ ] 可改進之處 * 最後問Interviewer：「有任何問題嗎？」有點奇怪 ## 4. 梅治玄 - 他評03 ### interviewer 優點 - 對問題的描述清晰 - 在討論題目的過程中與interviewee互動良好 可改進處 - 可以用情境包裝題目避免直接使用leetcode原題（甚至是leetcode介面） ### interviewee 優點 - 對題目的提問很關鍵 可改進處 - [0:40](https://youtu.be/e26UBgzbv3A?t=40)把「整理一下思緒」改成「確認一下題目」會顯得較專業 其他建議 - 馬賽克有點跑掉 ## 5. 沐揚仁-sheep-他評 04 ### interviewer #### 優點 - 從一開始的互動到題目的設計都相當用心，非常自然 #### 可改進之處 - 優化的部分可以沿神多一點討論 ### interviewee #### 優點 - 對題目的提問很非常關鍵 - E的部分解釋很清楚，甚至有附上表格 - 有注意排版 - 在書寫程式碼的過程中對程式碼的解釋也相當清楚 #### 可改進之處 - 英文口說可以更自信一點