😇：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

/**
 * 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 使用疊代

😇：你的函式執行需要較多次數的函式呼叫，如果呼叫層數比較深，需要增加額外的堆疊處理，還有可能出現堆疊溢位的情況，會對執行效率有一定影響，你有解決辦法嗎？

😊：確實，當遞迴太深的時候可能就會造成記憶體的問題。
我想使用迭代的方式解決這題，並使用堆疊來模擬遞迴，這樣比較好監測與預防堆疊溢位的狀況。

😇：那就麻煩你演示一下「堆疊來模擬遞迴」的部分

😊：沒問題

/**
 * 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```不需要重新輸入，你有想法嗎？

😊:我想給予運算符號假想的數值，再利用二元搜尋樹的特性：
*若任意節點的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值；若任意節點的右子樹不空，則右子樹上所有節點的值均大於它的根節點的值；*
來確保計算過程能維持「先乘除後加減」等運算規則並且避免數字與數字之間缺乏運算符號造成錯誤。
😊：所以我會加設原本的數學運算式已經被存在一個二元搜尋樹中，我只需要照規則將數字或運算符號插入即可。
😇：有料，請開始你的表演

/**
 * 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），所以對我而言遞迴解較為直觀。
不過若在記憶體空間上有所考量（遞迴方法會使用更多的堆疊空間），迭代也不失為一個好方法。
😇：了解，感謝你今天的參與。