課堂問答簡記: 2022-10-18

案例: 104. Maximum Depth of Binary Tree

Q1: 問題在哪裡? 如何舉例? 如何驗證?
- 4:25 舉例花太多時間: 可以舉更簡單的例子說明，以下圖為例：從 A 開始先往左邊找，B 也先往左邊找，為 NULL 因此檢查 B 的右邊，亦為 NULL 因此回到 A，接著找 A 的右邊，為 NULL，結束。
```
    A
   /
  B
```
- 2:50 舉例時可以先用英文字母 ABC 取代數字，這樣用英語面試比較不容易口誤。
- 9:02 驗證花太久時間 (4分半鐘): 以遞迴的方法來說，我們在意兩個條件，一是遞迴關係式，二是終止條件。因此在舉例驗證時可以直接舉開頭的節點來說明遞迴關係，接著舉一個 leaf node 說明遞迴終止條件，其他的節點可以用『以此類推』代過，節省面試時間 (因為後面可能還有 2, 3 題 followup 等你來解)

Q2: DPS/BFS 解法

BFS 解法
- 好處
  - 程式碼彈性較大，如果 followup 出一個變化題 (e.g., 找到 binary tree 的某個節點並刪除) 可以透過小修改當前程式碼快速實作完成，節省時間，以免後續 followup 解不完。
- 壞處
  - 程式碼相對較長
  - 思路相對不直覺

































// BFS
int maxDepth(TreeNode *root) {
    std::queue<TreeNode*> q;
    int level = 0;
    int cur_count;
    
    if (root) {
        q.push(root);
        cur_count = 1;
    } 
    while (!q.empty()) {
        // Pop first element from queue.
        auto ptr = q.front();
        q.pop();
        cur_count--;
        
        // Push children to queue.
        if (ptr->left) {
            q.push(ptr->left);
        }
        if (ptr->right) {
            q.push(ptr->right);
        }
        
        // Elements in the current level is 
        // traversed. Advance to next level.
        if (cur_count == 0) {
            cur_count = q.size();
            level++;
        }                
    }
    return level;
}

(點擊展開: BFS 方法 2) 利用 NULL 判斷 all current level nodes popped out，程式碼會再精簡一點

BFS Algorithm:

Initial state: enqueue root and enqueue NULL (use NULL to record all current level nodes have marked)
Iterative state:
- dequeue front node v
- for all edges from v to w in G.adjacentEdges(v) exist
  - enqueue child node w
- if v is NULL, then depth++
  - if q is not empty, enqueue NULL
  - else return depth

int maxDepth(TreeNode *root) {
    std::queue<TreeNode*> q;
    int depth = 0;

    if (root) {
        q.push(root);
        q.push(NULL);
    }

    while (!q.empty()) {
        // Pop first element from queue.
        auto v = q.front();
        q.pop();

        // Push children to queue.
        if (v) {
            if (v->left)
                q.push(v->left);
            if (v->right)
                q.push(v->right);
        }
        // Current level nodes have traversed.
        // Advance to next level.
        else {
            depth++;
            // if queue is empty, mean this is bottom.
            if (!q.empty()) 
                q.push(NULL);
        }            
    }
    return depth;
}

BFS 解刪除 binary 指定結點，只要新增 18 ~ 27 行。










































// Find the node with value equal to target. 
// If you found it, delete that node and its children.
int deleteNode(TreeNode *root, int target) {
    std::queue<TreeNode*> q;
    int level = 0;
    int cur_count;
    
    if (root) {
        q.push(root);
        cur_count = 1;
    } 
    while (!q.empty()) {
        
        auto ptr = q.front();
        q.pop();
        cur_count--;
        
        // Add this.
        if (ptr->left && ptr->left->value == target) {
            ptr->left = nullptr;
            break;
        }
        // Add this.
        if (ptr->right && ptr->right->value == target) {
            ptr->right = nullptr;
            break;
        }
        
        if (ptr->left) {
            q.push(ptr->left);
        }
        if (ptr->right) {
            q.push(ptr->right);
        }
        
        if (cur_count == 0) {
            cur_count = q.size();
            level++;
        }                
    }
    return level;
}

DFS (遞迴) 的解法
- 好處：
  - 程式碼較 BFS 簡潔
  - 思路直覺
- 壞處：
  - 遞迴深度過深記憶體會出問題
  - 面對 followup 的變化題較無彈性，沒辦法透過小小的修改程式碼解決變化題

案例: 9. Palindrome Number

秘客-Cypto

案例: 217. Contains Duplicate

起司堡-cheeseburger

Q1: 若不能用 hash table，那要用甚麼策略?

排序 -> x
set
priority queue
merge sort合併時檢查是否有相同數字
不要過度糾結於複雜度，更重要的是展現靈活應變

可以於建立 Heap 的過程中都檢查 current node 與 children nodes 是否有重複的數值，便有機會提早找到。完整建立 Heap

O (\frac{n}{2})

。若未找到，則後續再使用 Heap Sort

O (n \cdot \log_{2} n)

。以下提供 C 語言實作參考:

// build a maxheap O(n/2) 
// heap sort O(n * logn)
void swap(int *a, int *b) 
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

// top-down, recurrsion
bool heapify(int *heap, int heapSize, int parentIndex) 
{
    // base case
    int candidateIndex = parentIndex;
    int leftchildIndex = 2 * parentIndex + 1;
    int rightchildIndex = 2 * parentIndex + 2;
    if ((leftchildIndex < heapSize) && heap[leftchildIndex] > heap[candidateIndex])
        candidateIndex = leftchildIndex;
    if ((rightchildIndex < heapSize) && heap[rightchildIndex] > heap[candidateIndex])
        candidateIndex = rightchildIndex;
    if (candidateIndex == parentIndex)
        return false;

    // recurrsive steps
    // early stop
    if ((heap[parentIndex] == heap[leftchildIndex]) || (heap[parentIndex] == heap[leftchildIndex]))
        return true;
    // heapify
    swap(&heap[candidateIndex], &heap[parentIndex]);
    return heapify(heap, heapSize, candidateIndex);
}

bool containsDuplicate(int *nums, int numsSize)
{ 
    for (int i = (numsSize-2) / 2; i >= 0; i--) {
        // build heap O(n/2)
        if (heapify(nums, numsSize, i)) // early stop
            return true; 
    }

    for (int tail = numsSize-1; tail > 0; tail--) {
        // heap sort O(n * logn)
        swap(&nums[0], &nums[tail]);
        if (heapify(nums, tail, 0))// early stop, tail equal current heap size
            return true; 
        if (nums[0] == nums[tail]) // early stop
            return true; 
    }

    return false;
}