递归-算法入门
递归-概述
递归这一个词可以拆开来看，递：递推，归：回归(回溯)，而且递归的方式往往与树紧密结合着，树是一种从现实中抽象而来的数据结构，递归又是解决树的一种重要方法，例如最基本的树的三大遍历方式，递归的方式也两种，自顶向下和从底而上。通过leetcode上的一些例题来深入了解一下递归解决问题的方式。
递推与回溯
路径总和
题目描述：
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false。注：叶子节点 是指没有子节点的节点。
解决方案：
class Solution {
public:
int cnt = 0, res = INT_MIN;
bool flag = false;//用于结束不必要的判断
void dfs(TreeNode* r, int t) {
if (!r || flag) return;
cnt += r->val;
//cout << cnt <<endl;测试代码
if (cnt == t && !r->left && !r->right){
res = t;
flag =true;
}
//cout << "res:" << res << endl; 测试代码
dfs(r->left, t);
if (r->left)cnt -= r->left->val;
dfs(r->right, t);
if(r->right) cnt -= r->right->val;
}
bool hasPathSum(TreeNode* root, int targetSum) {
dfs(root, targetSum);
if (res == targetSum) return true;
else return false;
}
};
分析：
这里我们主要讲递推和回溯的过程，题目中递推的结束条件是到叶子节点处，我们这里习惯性采用前序的方式开始，具体递归情况可以自己测试，就很清楚了，回溯的话，就是一个返回上一步需要恢复现场的过程，具体题目的话，递归后把结果减去，回到原来的值。这个题目结束后，还可以试着尝试以下题目，本质上并无区别 路径总和二
递归与树
树的前序遍历，中序遍历，后序遍历：
前序：
void dfs(Treeroot* root) {
cout << cur->val << endl;//cur是当前遍历到的结点,因为示范，这一步操作是输出，还可以改为其他操作
dfs(cur->left);
dfs(cur->right);
}
中序：
void dfs(Treeroot* root) {
dfs(cur->left);
cout << cur->val << endl;//cur是当前遍历到的结点,因为示范，这一步操作是输出，还可以改为其他操作
dfs(cur->right);
}
后序：
void dfs(Treeroot* root) {
dfs(cur->left);
dfs(cur->right);
cout << cur->val << endl;//cur是当前遍历到的结点,因为示范，这一步操作是输出，还可以改为其他操作
}
这个是最基本的树的遍历方式了，然后可以发现，某序的区别就和我们要进行的操作有关，例如，前序就是先进行操作后递归，以下有一些简单的题目锻炼
二叉树的最小深度
题目描述：
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
解决方案：
class Solution {
public:
int minDepth(TreeNode* r) {
if (!r) return 0;
if (!r->left && !r->right) return 1;//直接排除左右都空的情况
int m1 = minDepth(r->left), m2 = minDepth(r->right);
if (r->left == NULL || r->right == NULL) return 1 + m1 + m2;
return 1 + min(m1, m2);
}
};
分析：
这个题目看上去和二叉树的最大深度很像，直接return 1 + min(minDepth(r->left), minDepth(r->right))就可以了吗？肯定是不对的，因为左右子树可能为空,这样就会返回错误的答案，我们有三种情况，一个是左右子树全为空，说明是叶子节点，那么当前层数应该+1，其中有一个为空，return 1 + m1 + m2,其中必有一个为0，这样就排除了，左右可能为空的情况，如果左右子树都存在，则返回其中深度最小的那棵。
自顶向下和从底而上
平衡二叉树
题目描述：
解决方案：
自顶而下(前序)
class Solution {
public:
int dfs(TreeNode* r) {
if (!r) return 0;
return 1 + max(dfs(r->left), dfs(r->right));
}
bool isBalanced(TreeNode* root) {
if (!root) return true;
int t = abs(dfs(root->left) - dfs(root->right));
if (t > 1) return false;
return isBalanced(root->left) && isBalanced(root->right);
}
};
从底而上(后序)
class Solution {
public:
int dfs(TreeNode* r) {
if (!r) return 0;
int hleft = dfs(r->left);
int hright = dfs(r->right);
if (hleft == -1 || hright == -1 || abs(hleft - hright) > 1)
return -1;
else return 1 + max(hleft, hright);
}
bool isBalanced(TreeNode* root) {
if(dfs(root) >= 0) return true;
else return false;
}
};
分析：
第一种方式很好理解，遍历到一个结点，就算出他们的左右子树的高度，做减法后比较是否大于1，然后继续递归左子树和右子树，很明显的发现，其中有重复计算，最坏的情况时间复杂度为o(n*n)，如何优化到o(n)呢，采用第二种方法，采用类似后序遍历的方式，先到树的底层，往上计算每一个结点的深度，就可以避免重复计算。
二叉树展开为链表
题目描述：
解决方案：
自顶向下暴力法：
class Solution {
public:
vector<TreeNode*> list;
void dfs(TreeNode* r) {
if (!r) return;
list.push_back(r);
dfs(r->left);
dfs(r->right);
}
void flatten(TreeNode* root) {
if (!root) return;
dfs(root);
int n = list.size();
for (int i = 0; i < n - 1; ++i) {
TreeNode* prev = list[i];
TreeNode* cur = list[i + 1];
prev->left = nullptr;
prev->right = cur;
}
}
};
模拟式连接：
class Solution {
public:
void flatten(TreeNode* root) {
if (!root) return;
while (root) {
if(root->left) {
TreeNode* pre = root -> left;
while (pre -> right) pre = pre -> right;
pre -> right = root -> right;
root -> right = root -> left;
root -> left = NULL;
}
root = root -> right;
}
}
};
从底而上智取：
class Solution {
public:
TreeNode* pre = NULL;
void flatten(TreeNode* root) {
if (!root) return;
flatten(root -> right);
flatten(root -> left);
root -> right = pre;
root -> left = NULL;
pre = root;
}
};
分析
第一种方法，也就是我能想到的方法，就是开一个动态数组，边遍历整个链表，边改变指向存下来，空间复杂度很高，第二种方法，采用前序的思想，每次把结点的左子树当作当前结点右子树，并且将该左子树的最右端结点与之前的右子树连接(很难想到)，第三种方法，是我看到一位大佬的，采用自底而上的方式后序遍历整棵树，然后改变树的结构。为什么前序不行呢？因为前序随着树的结构的改变会遍历不到一部分数据，简单又利落的解决问题！