- 什么是递归?
函数自己调用自己的情况 - 为什么会用到递归?
本质:在解决主问题的时候衍生出一个相同处理过程的子问题,子问题再继续衍生子问题… - 如何理解递归?
- 第一层次的理解:递归展开的细节图
- 第二层次的理解:二叉树题目练习
- 第三层次的理解:宏观看待递归过程
- a. 不要再在意递归的细节展开图
- b. 把递归的函数当成一个黑盒
- c. 相信这个黑盒一定能完成既定任务
- 如何写好一个递归?
- a. 先找到主问题和子问题的相同处理过程!!!-> 可以用于处理函数头的设计
- b. 只关心某一个子问题是如何解决的 -> 可以用于处理函数体的书写
- c. 注意一下递归函数的出口即可\
- 汉诺塔问题
找到主问题和子问题的相同处理过程 -> 用于处理函数头的设计:
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);
}
- 合并两个有序链表
找到主问题和子问题的相同处理过程 -> 用于处理函数头的设计:
合并两个有序链表 -> 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;
}
}
- 反转链表
找到主问题和子问题的相同处理过程 -> 用于处理函数头的设计:
反转一个链表 -> 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;
}
- 两两交换链表中的节点
找到主问题和子问题的相同处理过程 -> 用于处理函数头的设计:
两两交换链表中的节点 -> 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;
}
- 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);
}
- 计算布尔二叉树的值
找到主问题和子问题的相同处理过程 -> 用于处理函数头的设计:
返回一棵完整二叉树的布尔值 -> 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);
}
- 求根节点到叶节点数字之和
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);
}
- 二叉树剪枝
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;
}
- 验证二叉搜索树
二叉搜索树的中序遍历是有序的
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);
}
- 二叉搜索树中第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;
}
- 二叉树的所有路径
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;
}