# Recursion I

###### tags: `LeetCode筆記`

## :memo: 一、特性

### 1. recurrence relation
一系列規則使遞迴發生到終止狀況

### 2. base case
終止狀況使遞迴不再繼續產生

### Pascal's Triangle:
* recurrence relation:

* base case:


### 寫成code又是另一件難度的事了

## :memo: 二、基本知識
**fmax(a,b)** // C語言函式回傳a,b中最大值
**long long** // 8bytes 值:-9223372036854775808 至 9223372036854775807

## :memo: Tips
- **When in doubt, write down the recurrence relationship.**

- **Whenever possible, apply memoization.**

- **When stack overflows, tail recursion might come to help.**

## :memo: 三、Memoization

### 利用此技術去減少重複計算(空間換時間)
重複計算會長這樣:

### Top-Down Memoization

if (cache[n] != 0)
{
    return cache[n];
}

cache[n] = fib(n-1) + fib(n-2);

return cache[n];

### Bottom-Up Tabulation

if (n <= 1)
{
    return n;
}

for (int i = 0; i < n; i++)
{
    cache[n] = cache[n - 1] + cache[n - 2];
}

return cache[n];

### 更快要用數學方法(log(N))

class Solution {
    public int fib(int N) {
        double goldenRatio = (1 + Math.sqrt(5)) / 2;
        return (int) Math.round(Math.pow(goldenRatio, N) / Math.sqrt(5));
    }
}

## :memo: *Search in a Binary Search Tree (Easy)


### 作法
在function一開始初始化一個指標指向NULL，先判斷是否該node的val為要找的val，是就回傳root，不是就往左子樹遞迴(記得先檢查左子樹不等於NULL)，p = searchBST(root->left,val)，回傳p後，檢查p不等於NULL就再回傳p。左子樹是NULL，就往右子樹做同樣操作。

struct TreeNode* searchBST(struct TreeNode* root, int val) {
    struct TreeNode* p = NULL;
    
    if (root->val == val)
    {
        return root;
    }
    if (root->left != NULL)
    {
        p = searchBST(root->left, val);
        if (p != NULL)
        {
            return p;    
        }        
    }
    if (root->right != NULL)
    {
        p = searchBST(root->right, val);
        if (p != NULL)
        {
            return p;    
        }        
    }
    
    return p;
}

### 作法 三元運算子

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {        
        if (root == nullptr || root->val == val) {
            return root;
        }
        
        return val < root->val ? searchBST(root->left, val) : searchBST(root->right, val);
    }
};

## :memo: *Maximum Depth of Binary Tree (Easy)
找樹的高度

int maxDepth(struct TreeNode* root){
    if (root == NULL)
    {
        return NULL;
    }
    
    return fmax(maxDepth(root->left) + 1, maxDepth(root->right) + 1);
}

## :memo: *Reverse String (Easy)

### 作法 recursion

class Solution {
public:
    void reverseString(vector<char>& s) {
        helper(s, s.size() - 1, 0);
    }
    void helper(vector<char>& s, int end, int start) {
        if (start >= end) {
            return;
        }
        
        char tmp = s[start];
        s[start] = s[end];
        s[end] = tmp;
        
        helper(s, end - 1, start + 1);
    }
};

### 作法 iteration
**時間: O(N)**
**空間: O(1)**

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        
        ListNode* prev = dummy;
        
        while (head != nullptr && head->next != nullptr) {
            ListNode* firstNode = head;
            ListNode* secondNode = head->next;
            
            prev->next = secondNode;
            firstNode->next = secondNode->next;
            secondNode->next = firstNode;
            
            prev = firstNode;
            head = firstNode->next;
        }
        
        return dummy->next;
    }
};

## :memo: *Reverse Linked List (Easy)


### 作法 recursion

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* p = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        
        return p;
    }
};

### 作法 iteration

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* current = head;
        ListNode* next = head;

        while (current != nullptr) {
            next = current->next;
            current->next = prev;
            prev = current;
            current = next;
        }
        
        return prev;
};

## :memo: *Pascal's Triangle II (Easy)


### 作法 recursion
**時間: O(2^k)**
**空間: O(k)**

class Solution {
 public:
    int getNum(int row, int col) {
        if (row == 0 || col == 0 || row == col) {
            return 1;
        }
        
        return getNum(row - 1, col - 1) + getNum(row - 1, col);
    }

    vector<int> getRow(int rowIndex) {
        vector<int> ans;

        for (int i = 0; i <= rowIndex; i++) {
            ans.push_back(getNum(rowIndex, i));
        }      

        return ans;
    }
};

### 作法 Memory-efficient Dynamic Programming
**時間: O(k^2)**
**空間: O(k)**

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> ans = vector<int>(rowIndex + 1, 1);

        for (int i = 1; i < rowIndex; i++) {
            for (int j = i; j > 0; j--) {
                ans[j] += ans[j - 1];  // ans[j] = ans[j - 1] + ans[j]
            }                
        }            

        return ans;
    }
};

### 作法 Math! (specifically, Combinatorics)
**時間: O(k)**
**空間: O(k)**

class Solution {
public:
    vector<int> getRow(int n) {
        vector<int> ans = {1};

        for (int k = 1; k <= n; k++) {
            ans.push_back((int)((ans.back() * (long long)(n - k + 1)) / k));      
        }     

        return ans;
    }
};

## :memo: *Climbing Stairs (Easy)

### 作法 Dynamic Programming
**時間: O(N)**
**空間: O(N)**

class Solution {
public:
    int climbStairs(int n) {
        int cache[46];
        
        cache[1] = 1;
        cache[2] = 2;
        
        for (int i = 3; i <= n; i++) {
            cache[i] = cache[i - 1] + cache[i - 2];
        }
    
        return cache[n];
    }
};

### 作法 Fibonacci Number
**時間: O(N)**
**空間: O(1)**

class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        
        int first = 1;
        int second = 2;
        for (int i = 3; i <= n; i++) {
            int third = first + second;
            first = second;
            second = third;
        }
        
        return second;
    }
};

## :memo: *Merge Two Sorted Lists (Easy)


### 作法 recursion

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {        
        if (list1 == nullptr) {
            return list2;
        }
        else if (list2 == nullptr) {
            return list1;
        }
        else if (list1->val < list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
        else {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};

## :memo: Swap Nodes in Pairs (Medium)


### 作法 recursion
**時間: O(N)**
**空間: O(N)**

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr) {
            return nullptr;
        }
        
        if (head->next == nullptr) {
            return head;
        }
        
        ListNode* p = head;
        if (head != nullptr && head->next != nullptr) {
            int tmp = head->val;
            head->val = head->next->val;
            head->next->val = tmp;
        }
        if (head->next->next != nullptr) {
            head = head->next->next;
            swapPairs(head);
        }
        
        head = p;
        
        return p;
    }
};

## :memo: Pow(x, n) (Medium)

### 作法 fastPow

double fastPow(double x, long long n) {
    if (n == 0) 
    {
        return 1.0;
    }
    double half = fastPow(x, n / 2);
    if (n % 2 == 0) 
    {
        return half * half;
    } 
    else 
    {
        return half * half * x;
    }
}

double myPow(double x, long long n){
    if (n < 0)
    {
        n = -n;
        x = 1.0 / x;
    }
    
    return fastPow(x, n);
}

## :memo: K-th Symbol in Grammar (Medium)
這題腦袋要靈活才可能想出來，用到XOR去表示遞迴，參考Dicuss才會寫，把圖形畫出來可以幫助理解(printf)
### 作法 範例

int kthGrammar(int n, int k){
    if (k <= 2)
    {
        return k - 1;
    }
    if (k % 2)
    {
        return kthGrammar(n, k / 2+1);
    }    
    else
    {
        return 1 ^ kthGrammar(n, k / 2);
    }
    
    return;
}

## :memo: *Unique Binary Search Trees II (Medium)


這一題找出所有大小等於n的樹的形狀，完全不知道怎麼寫，就算看到範例code也要花很長時間才能去消化吸收，範例code的架構很整齊但是要弄懂一定要去trace才行。

### 作法 範例code C

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* push(struct TreeNode*** arr, int* returnSize, int a) {
    struct TreeNode* t = NULL;
    if (a > -1) //only valid value can be allocated
    {
        t = (struct TreeNode*) malloc(sizeof(struct TreeNode));
        t->left = t->right = NULL;
        t->val = a;
    }
    *returnSize += 1;
    *arr = (struct TreeNode**)realloc(*arr, sizeof(struct TreeNode*) * (*returnSize));
    (*arr)[*returnSize-1] = t;
    return t; //return this node for -> root
}

struct TreeNode* generate(int begin, int end, int* returnSize){
    struct TreeNode** arr = (struct TreeNode**)malloc(sizeof(struct TreeNode*));
    if (begin>=end)
    {
        if (begin > end)
        {
            push(&arr, returnSize, -1);
        }
        if (begin == end)
        {
            push(&arr, returnSize, begin);
        }
        return arr;
    }
    for (int i = begin; i <= end; i++)
    {
        int count0 = 0;
        int count1 = 0;
        struct TreeNode** arr0 = generate(begin, i-1, &count0);
        struct TreeNode** arr1 = generate(i+1, end, &count1);
        for(int j = 0; j < count0; j++)
        {
            for(int k = 0; k < count1; k++)
            {
                struct TreeNode* t = push(&arr, returnSize, i);
                t->left = arr0[j];
                t->right = arr1[k];
            }
        }
    }
    return arr;
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
struct TreeNode** generateTrees(int n, int* returnSize){
    *returnSize = 0;
    if (!n)
    {
        return NULL;
    }
    
    return generate(1, n, returnSize);
}

### 作法 C++

class Solution {
public:
    vector<TreeNode *> generateTrees(int n) {
        return helper(1,n);
    }
    
    vector<TreeNode*> helper(int s, int e) {
        if (s > e) {
             return vector<TreeNode*>(1, NULL);
        }
        
        vector<TreeNode*> result;
        for (int i=s; i <= e; ++i) {
            vector<TreeNode*> left, right;
                left = helper(s, i - 1);
                right = helper(i + 1, e);
                for (int j = 0; j < left.size(); ++j) {
                    for (int k = 0; k < right.size(); ++k) {
                        TreeNode* root = new TreeNode(i);
                        root->left = left[j];
                        root->right = right[k];
                        result.push_back(root);
                    }
                }
        }
        
        return result;
    }
};

## :memo: 刷題檢討
解決遞迴題目之前要先將數學表示方式寫出來，再利用coding去寫成程式，trace檢查有沒有錯誤，解遞迴腦袋要靈活才想得出來!