【C++刷题】优选算法——递归第一辑

• 什么是递归？
  函数自己调用自己的情况
• 为什么会用到递归？
  本质：在解决主问题的时候衍生出一个相同处理过程的子问题，子问题再继续衍生子问题…
• 如何理解递归？
  • 第一层次的理解：递归展开的细节图
  • 第二层次的理解：二叉树题目练习
  • 第三层次的理解：宏观看待递归过程
    • a. 不要再在意递归的细节展开图
    • b. 把递归的函数当成一个黑盒
    • c. 相信这个黑盒一定能完成既定任务
• 如何写好一个递归？
  • a. 先找到主问题和子问题的相同处理过程！！！-> 可以用于处理函数头的设计
  • b. 只关心某一个子问题是如何解决的 -> 可以用于处理函数体的书写
  • c. 注意一下递归函数的出口即可\

1. 汉诺塔问题

找到主问题和子问题的相同处理过程 -> 用于处理函数头的设计:
	n个盘子，从A柱子，借助B柱子，移动到C柱子 -> void dfs(int n, vector<int>& A, vector<int>& B, vector<int>& C)

void dfs(int n, vector<int>& A, vector<int>& B, vector<int>& C)
{
    if(n == 1)
    {
        C.push_back(A.back());
        A.pop_back();
        return;
    }

    dfs(n-1, A, C, B);
    C.push_back(A.back());
    A.pop_back();
    dfs(n-1, B, A, C);
}
void hanota(vector<int>& A, vector<int>& B, vector<int>& C)
{
    dfs(A.size(), A, B, C);
}

2. 合并两个有序链表

找到主问题和子问题的相同处理过程 -> 用于处理函数头的设计:
	合并两个有序链表 -> ListNode* dfs(list1, list2);

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
{
    if(list1 == nullptr) return list2;
    else if(list2 == nullptr) return list1;

    if(list1->val <= list2->val)
    {
        list1->next = mergeTwoLists(list1->next, list2);
        return list1;
    }
    else
    {
        list2->next = mergeTwoLists(list1, list2->next);
        return list2;
    }
}

3. 反转链表

找到主问题和子问题的相同处理过程 -> 用于处理函数头的设计:
	反转一个链表 -> ListNode* dfs(list1);

ListNode* reverseList(ListNode* head)
{
    if(head == nullptr || head->next == nullptr) return head;

    ListNode* newHead = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}

4. 两两交换链表中的节点

找到主问题和子问题的相同处理过程 -> 用于处理函数头的设计:
	两两交换链表中的节点 -> ListNode* dfs(ListNode* list1)

ListNode* swapPairs(ListNode* head)
{
    if(head == nullptr || head->next == nullptr) return head;

    ListNode* newHead = head->next;
    head->next = newHead->next;
    newHead->next = head;
    head->next = swapPairs(head->next);
    return newHead;
}

5. Pow(x, n)

找到主问题和子问题的相同处理过程 -> 用于处理函数头的设计:
	求 x 的 n 次幂 -> int dfs(int x, int n);

double dfs(double x, int n)
{
    if(n == 0) return 1;
    
    double tmp = dfs(x, n / 2);
    return n % 2 ? tmp * tmp * x : tmp * tmp;
}
double myPow(double x, int n)
{
    if(n > 0) return dfs(x, n);
    else return 1 / dfs(x, n);
}

6. 计算布尔二叉树的值

找到主问题和子问题的相同处理过程 -> 用于处理函数头的设计:
	返回一棵完整二叉树的布尔值 -> bool dfs(TreeNode* root);

bool evaluateTree(TreeNode* root)
{
    if(root->val == 0) return false;
    else if(root->val == 1) return true;

    if(root->val == 2) return evaluateTree(root->left) || evaluateTree(root->right);
    else return evaluateTree(root->left) && evaluateTree(root->right);
}

7. 求根节点到叶节点数字之和

int dfs(TreeNode* root, int val)
{
    val = val * 10 + root->val;
    if(root->left == nullptr && root->right == nullptr) return val;

    int left = 0, right = 0;
    if(root->left) left = dfs(root->left, val);
    if(root->right) right = dfs(root->right, val);
    return left + right;
}
int sumNumbers(TreeNode* root)
{
    return dfs(root, 0);
}

8. 二叉树剪枝

TreeNode* pruneTree(TreeNode* root)
{
    if(root == nullptr) return nullptr;

    root->left = pruneTree(root->left);
    root->right = pruneTree(root->right);

    if(root->left == nullptr && root->right == nullptr && root->val == 0)
        return nullptr;
    return root;
}

9. 验证二叉搜索树

二叉搜索树的中序遍历是有序的

long long prev = LLONG_MIN;
bool isValidBST(TreeNode* root)
{
    if(root == nullptr) return true;
	
	// 剪枝
    if(isValidBST(root->left) == false) return false;
    
    if (prev < (root->val)) prev = root->val;
    else return false; // 剪枝

    return isValidBST(root->right);
}

10. 二叉搜索树中第K小的元素

int value = -1;
int count = 0;
void dfs(TreeNode* root)
{
    if(root == nullptr) return;

    dfs(root->left);

    if(count == 0) return;
    if(value < root->val)
    {
        value = root->val;
        --count;
    }

    dfs(root->right);
}
int kthSmallest(TreeNode* root, int k)
{
    count = k;
    dfs(root);
    return value;
}

11. 二叉树的所有路径

vector<string> v;
void dfs(TreeNode* root, string s)
{
    if(root->left == nullptr && root->right == nullptr)
    {
        s += to_string(root->val);
        v.push_back(s);
        return;
    }

    s += to_string(root->val);
    s += "->";
    if(root->left) dfs(root->left, s);
    if(root->right) dfs(root->right, s);
}
vector<string> binaryTreePaths(TreeNode* root)
{
    dfs(root, "");
    return v;
}