## LeetCode 模擬面試練習

### [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:
我的做法是遞迴。從根節點開始，如果新的值小於當前節點的值，我將向左遞迴；如果新的值大於當前節點的值，我將向右遞迴。當達到一個空節點時，我將在這裡插入新的節點。

// 定義二元搜尋樹的節點結構
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:
讓我來測試一下代碼是否能順利運行

#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的部分解釋很清楚，甚至有附上表格
- 有注意排版
- 在書寫程式碼的過程中對程式碼的解釋也相當清楚
#### 可改進之處
- 英文口說可以更自信一點