干货满满！全面详解如何用递归解题( 三 ) _递归

public int f(int n) {if (n == 1) return 1;if (n == 2) return 2;int result = 0;int pre = 1;int next = 2;for (int i = 3; i < n + 1; i ++) {result = pre + next;pre = next;next = result;}return result;}改造后的时间复杂度是 O(n), 而由于我们在计算过程中只定义了两个变量（pre，next），所以空间复杂度是O(1)
简单总结一下：分析问题我们需要采用自上而下的思维，而解决问题有时候采用自下而上的方式能让算法性能得到极大提升,思路比结论重要

初级题接下来我们来看下一道经典的题目: 反转二叉树将左边的二叉树反转成右边的二叉树

文章插图
接下来让我们看看用我们之前总结的递归解法四步曲如何解题
1.定义一个函数，这个函数代表了翻转以 root 为根节点的二叉树

public static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }}public TreeNode invertTree(TreeNode root) {}

2.查找问题与子问题的关系,得出递推公式我们之前说了，解题要采用自上而下的思考方式，那我们取前面的1， 2，3 结点来看，对于根节点 1 来说，假设 2, 3 结点下的节点都已经翻转，那么只要翻转 2， 3 节点即满足需求

文章插图
对于2， 3 结点来说，也是翻转其左右节点即可,依此类推,对每一个根节点，依次翻转其左右节点，所以我们可知问题与子问题的关系是翻转(根节点) = 翻转(根节点的左节点) + 翻转(根节点的右节点)即
invert(root) = invert(root->left) + invert(root->right)
而显然递归的终止条件是当结点为叶子结点时终止（因为叶子节点没有左右结点）
3.将第二步的递推公式用代码表示出来补充到步骤 1 定义的函数中

public TreeNode invertTree(TreeNode root) {// 叶子结果不能翻转if (root == ) {return ;}// 翻转左节点下的左右节点TreeNode left = invertTree(root.left);// 翻转右节点下的左右节点TreeNode right = invertTree(root.right);// 左右节点下的二叉树翻转好后，翻转根节点的左右节点root.right = left;root.left = right;return root;}

4.时间复杂度分析由于我们会对每一个节点都去做翻转，所以时间复杂度是 O(n)，那么空间复杂度呢，这道题的空间复杂度非常有意思，我们一起来看下，由于每次调用 invertTree 函数都相当于一次压栈操作，那最多压了几次栈呢，仔细看上面函数的下一段代码
TreeNode left = invertTree(root.left);从根节点出发不断对左结果调用翻转函数, 直到叶子节点，每调用一次都会压栈，左节点调用完后，出栈，再对右节点压栈....,下图可知栈的大小为3，即树的高度，如果是完全二叉树，则树的高度为logn, 即空间复杂度为O(logn)

文章插图
最坏情况，如果此二叉树是如图所示(只有左节点，没有右节点)，则树的高度即结点的个数 n，此时空间复杂度为 O(n),总的来看，空间复杂度为O(n)

文章插图
说句题外话，这道题当初曾引起轰动，因为 mac 下著名包管理工具 homebrew 的作者 Max Howell 当初解不开这道题，结果被 Google 拒了，也就是说如果你解出了这道题，就超越了这位世界大神，想想是不是很激动
中级题
接下来我们看一下大学时学过的汉诺塔问题：如下图所示，从左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数

文章插图
接下来套用我们的递归四步法看下这题怎么解
1.定义问题的递归函数，明确函数的功能,我们定义这个函数的功能为：把 A 上面的 n 个圆盘经由 B 移到 C
// 将 n 个圆盘从 a 经由 b 移动到 c 上public voidhanoid(int n, char a, char b, char c) {}2.查找问题与子问题的关系首先我们看如果 A 柱子上只有两块圆盘该怎么移

文章插图
前面我们多次提到，分析问题与子问题的关系要采用自上而下的分析方式，要将 n 个圆盘经由 B 移到 C 柱上去，可以按以下三步来分析* 将上面的 n-1 个圆盘看成是一个圆盘,这样分析思路就与上面提到的只有两块圆盘的思路一致了* 将上面的 n-1 个圆盘经由 C 移到 B* 此时将 A 底下的那块最大的圆盘移到 C* 再将 B 上的 n-1 个圆盘经由A移到 C上