递归这一个词可以拆开来看，递：递推，归：回归(回溯)，而且递归的方式往往与树紧密结合着，树是一种从现实中抽象而来的数据结构，递归又是解决树的一种重要方法，例如最基本的树的三大遍历方式，递归的方式也两种，自顶向下和从底而上。通过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 <
分析：
这里我们主要讲递推和回溯的过程，题目中递推的结束条件是到叶子节点处，我们这里习惯性采用前序的方式开始，具体递归情况可以自己测试，就很清楚了，回溯的话，就是一个返回上一步需要恢复现场的过程，具体题目的话，递归后把结果减去，回到原来的值。这个题目结束后，还可以试着尝试以下题目，本质上并无区别 路径总和二
树的前序遍历，中序遍历，后序遍历：
前序：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 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; }};
分析
第一种方法，也就是我能想到的方法，就是开一个动态数组，边遍历整个链表，边改变指向存下来，空间复杂度很高，第二种方法，采用前序的思想，每次把结点的左子树当作当前结点右子树，并且将该左子树的最右端结点与之前的右子树连接(很难想到)，第三种方法，是我看到一位大佬的，采用自底而上的方式后序遍历整棵树，然后改变树的结构。为什么前序不行呢？因为前序随着树的结构的改变会遍历不到一部分数据，简单又利落的解决问题！