貢獻者: 德米安 Demi
video
🧔:interviewer 👶:interviewee
影片: 00:19
🧔:希望Demi能夠實作一個function,輸入binary tree並回傳一個invert binary tree。
👶:好的那我們要處理invert binary tree的問題,好比如我要將:
👶:另外也必須特別考量到空集合的狀況。
👶:我剛開始想到的方法是用遞迴的方式,以postorder的方式先向下找節點,如果有子節點時即向下執行函數,直到到達樹葉,或是已訪問完自己的子節點後,即對自己的左右子節點做交換。最後直到根節點完成交換後即結束全部的遞迴函數。
🧔:這樣的時間複雜度是如何?
👶:由於需要遞迴的訪問每一個節點執行函數,故時間複雜度為
struct tree{
int val;
struct tree *left;
struct tree *right;
}
struct tree *invertBtree(struct tree * root) {
if(root->left) root->left = invertBtree(root->left);
if(root->right) root->right = invertBtree(root->right);
sturct tree *temp;
temp = root->left;
root->left = root->right;
root->right = temp;
}
🧔:想請問是否有不是 recursive 的做法呢?
👶:我的想法是可以透過一個 linked list 的 stack 對我們要做 invert 的 node 做紀錄,將搜尋到的node紀錄在stack中,再逐一從stack中的node做invert,以使用iterative達到類似recursive的做法。
struct tree{
int val;
struct tree * left;
struct tree * right;
}
struct treestack{
struct tree* cur;
struct tree* next;
}
struct tree * invertbtree(struct tree * root){
if(!root) return 0;
struct treestack* tstack;
tstack->cur = root;
while(tstack->cur){
if (tstack->cur->left || tstack->cur->right ) {
//預期做tstack紀錄的動作,提供else階段pop tstack節點
}
else{
sturct tree* temp;
temp = tstack->cur-> left;
tstack->cur-> left = tstack->cur->right;
tstack->cur->right =temp;
tstack->next = tsack->cur->next;
tstack->cur = tstack->next;
}
}
}
延伸閱讀: Invert binary tree in O(1) space without stack/queue/recursion
影片: 16:38
🧔:在第二題我會提供一個int array和一個int target,我希望你可以回傳給我此target在array的index,若target不在array中,則告訴我如果target插入array時,他的index是多少?我希望你可以在
👶:這一題最直覺的方法是使用Sequential Search的方式一個一個找值,然而這個方法的時間複雜度為
👶:每次在尋找前紀錄首尾index的區間,並比較中間index的值與target的大小,若arr[index]>target,則往左側區間找值,反之往右,如果相同則回傳該index。直到區間小於一,直接做大小的比較來回傳index。
int bsearch(int * arr, int target){
int head = 0;
int tail = sizeof(arr)/ sizeof(int) -1;
int cur;
while(tail-head>1){
cur = head + (tail - head)/2;
if(arr[cur] > target) tail =cur-1;
else if (arr[cur] < target) head = cur+1;
else return cur;
}
if(arr[head] >= target) return head;
else if(arr[tail] >= target ) return tail;
else return tail+1;
}
影片: 28:07
🧔:最後希望你能實作一個power function,即是
👶:這一題要實作
最直覺的作法是用for迴圈讓
double power(double x , int n){
if(x ==1) return 1;
else if (x == 0) return 0;
if(n == 0 ) return 1;
double result;
if(n/2){
result = power(x, n/2);
result *= result;
}
else result = 1;
if(n%2){
if(n>0) result *= x;
else result /= x;
}
return result;
}
延伸閱讀: LeetCode 50. Pow(x, n)
針對 interviewer 的檢討:
struct TreeNode *invertTree(struct TreeNode *root) {
if (!root) return NULL;
struct TreeNode *l = invertTree(root->left), *r = invertTree(root->right);
root->left = r, root->right = l;
return root;
}
arr_size
),應該適度打斷,討論 C 語言函式呼叫的議題,畢竟光靠一個傳入的指標,該如何知道陣列具體的空間呢?int searchInsert(int *nums, int numsSize, int target) {
int lo = 0, hi = numsSize;
while (lo < hi) {
int m = lo + (hi - lo) / 2;
if (nums[m] < target)
lo = m + 1;
else
hi = m;
}
return lo;
}
int *arr; int tail = sizeof(arr) / sizeof(int) - 1;
這樣的程式碼時,應該要打斷,畢竟 sizeof(arr)
存在嚴重的錯誤
ARRAY_SIZE
巨集」一節double myPow(double x, int n) {
double value = 1;
long nn = n;
if (nn < 0) {
for (nn *= -1; nn; nn >>= 1) {
if (nn & 1)
value /= x;
x *= x;
}
return value;
}
for (; nn; nn >>= 1) {
if (nn & 1)
value *= x;
x *= x;
}
return value;
}
針對 interviewee 的檢討:
struct btree *temp; temp = root->left;
可改為 struct btree *tmp = root->left;
。不要小看只是幾個字元的差距,因為在 Google Docs 中,程式碼的縮排都要自己處理,越少換行或者非必要的 tab 按鍵,都可避免說話和程式碼撰寫間的落差struct TreeNode { struct TreeNode *left, *right; }
注意 bintree
的命名,從而避免跟 B-Tree 混淆。星號 (asterisk, 即 *
) 作為指標的宣告一部分,應靠向變數名稱,這樣不僅可寫出更緊湊的程式碼,也能避免混淆。在 03:36 誤將 binary tree 講成 B-Tree,也該改進==
讀作「等於」即可,也可說「判斷是否相等」,簡潔的讀法習慣有助於英語表達