• 什么是递归?
    函数自己调用自己的情况
  • 为什么会用到递归?
    本质:在解决主问题的时候衍生出一个相同处理过程的子问题,子问题再继续衍生子问题…
  • 如何理解递归?
    • 第一层次的理解:递归展开的细节图
    • 第二层次的理解:二叉树题目练习
    • 第三层次的理解:宏观看待递归过程
      • 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);
}
  1. 合并两个有序链表
找到主问题和子问题的相同处理过程 -> 用于处理函数头的设计:
	合并两个有序链表 -> 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;
    }
}
  1. 反转链表
找到主问题和子问题的相同处理过程 -> 用于处理函数头的设计:
	反转一个链表 -> 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;
}
  1. 两两交换链表中的节点
找到主问题和子问题的相同处理过程 -> 用于处理函数头的设计:
	两两交换链表中的节点 -> 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;
}
  1. 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);
}
  1. 计算布尔二叉树的值
找到主问题和子问题的相同处理过程 -> 用于处理函数头的设计:
	返回一棵完整二叉树的布尔值 -> 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);
}
  1. 求根节点到叶节点数字之和
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);
}
  1. 二叉树剪枝
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;
}
  1. 验证二叉搜索树
二叉搜索树的中序遍历是有序的
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);
}
  1. 二叉搜索树中第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;
}
  1. 二叉树的所有路径
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;
}
05-11 10:12