2022 年「資訊科技產業專案設計」作業 4

貢獻者: 本丸 RiceBall 胖達-Panda

230. Kth Smallest Element in a BST

模擬面試連結:https://www.youtube.com/watch?v=doKvnpNxg2M

🐼：interviewer
🐶：interviewee

🐼：Hello I am your interviewer today . Today I want to discuss some problems with you. And I hope you can solve them by writting some code on CodeShare. Here is the problem. You are given the root of a Binary Search Tree and an integer k.Please find the kth smallest element in the tree.I have included an example for your reference.

// Given the root of a binary search tree, and an integer k, 
// return the kth smallest value of all the values of thenodes in the tree.
               3
              / \
             1   4 
              \
               2
// root=[3,1,4,NULL,2] , k=1   return 1

🐶：oh, yu mean if k is 1 and then i will return the node value 1. And if k is 3 it will return the node here and its value is 3.

k=1  val=1
k=3  val =3

🐼：So do you have any idea solving the problem?

🐶：i wanna find kth element by DFS and we know node have two children：left right if the root's value is not NULL , i will find the left first ,if cheked left already counting 1 plus，and than need chek the count number ,find the right side.

🐼：This approach sounds reasonable,you can start to code now

  int count=0;
  int ans;
  
  void DFS(TreeNode* root, int k){
  	if(root == NULL)
    	return;
    DFS(root->left, k);
    count++;
    if(count == k){
    	ans = root->val;
      return;
    }
    DFS(root->right, k);
  }
  
  int Ksmall(TreeNode* root, int k){
  	DFS(root, k);
    return ans;
  }

🐼：Can you analyze the time and space complexity of your solution?
🐶：time complexity O(k), space complexity O(n)
🐼：We always use DFS and BFS for binary tree traversal. Do you think you can use BFS to solve the problem?
🐶：because BFS is go left and right both, and the structure of BST is all left nodes are smaller than root. if k is at the left side BFS will waste time at the right side.

改進方案

使用英文對答會遇到幾個問題：

1. 聽不懂，這邊感謝🐼英文想當容易理解
2. 聽得懂，知道怎麼回答，不會用英文回答
3. 聽得懂，不知道怎麼回答

在這個次作業中大多數是屬於2的情形，也不是說不會講，而是在沒有準備大綱或草稿的情況下腦袋容易打結，如：comlexity的部分，後續把較細部的回答方式稍微記錄下來才比較流暢的回答。

學期表現檢討

REACTO說來容易做來難，也很花費時間。常常拖延症發坐起來有些作業沒能在規定時間完成。從年中才開始學程式，整個學期的過程對我來說不是overloading也是hardloading。

檢討interviewee的話，不論是中文還是英文回答，在說話的節奏上常常會卡很久或是講太快(講太快的原因可能歸咎於緊張與不熟練)，coding的速度太慢以及比起解釋延伸問題，對現在的我來說反而是延伸問題是什麼。

扮演interviewer這個腳色時難度反而是最高的，要問什麼問題，這樣的問題如果不按照leetcode的題目去講應該怎麼講，實務上會用到這個嗎?事實上我沒有任何實務的經驗，對於相關議題的了解也不夠深入，最後往往是leetcode的換個說法而已。