---
tags: INFO2022
---

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

## 案例: [104. Maximum Depth of Binary Tree](https://leetcode.com/problems/maximum-depth-of-binary-tree/)
* [噠噠特工-LonelyBoy](https://hackmd.io/@sysprog/S1gP445eGs)
* Q1: 問題在哪裡? 如何舉例? 如何驗證?
* [4:25](https://www.youtube.com/watch?v=sd2SuF743PI&t=4m25s) 舉例花太多時間: 可以舉更簡單的例子說明，以下圖為例：從 A 開始先往左邊找，B 也先往左邊找，為 NULL 因此檢查 B 的右邊，亦為 NULL 因此回到 A，接著找 A 的右邊，為 NULL，結束。

            A
           /
          B

* [2:50](https://www.youtube.com/watch?v=8FgfWqh54OE&t=2m50s) 舉例時可以先用英文字母 ABC 取代數字，這樣用英語面試比較不容易口誤。
* [9:02](https://www.youtube.com/watch?v=sd2SuF743PI&t=9m02s) 驗證花太久時間 (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;
        }

:::spoiler **(點擊展開: BFS 方法 2)** 利用 NULL 判斷 all current level nodes popped out，程式碼會再精簡一點
:::info
[**BFS Algorithm**](https://en.wikipedia.org/wiki/Breadth-first_search):
* **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](https://leetcode.com/problems/palindrome-number/)
* [秘客-Cypto](https://hackmd.io/@sysprog/BkG_gclMs)

## 案例: [217. Contains Duplicate](https://leetcode.com/problems/contains-duplicate/)
* [起司堡-cheeseburger](https://hackmd.io/@sysprog/Bkdiazbzs)
* 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;
            }