程序员必备的基本算法：递归详解( 三 )
文章插图
显然 ， 「递推关系式」就是：
invertTree（root）= invertTree（root.left） + invertTree（root.right）;【程序员必备的基本算法：递归详解】于是 ， 很容易可以得出以下代码：
//翻转一颗二叉树public TreeNode invertTree(TreeNode root) {if(root==null || (root.left ==null}//翻转左子树TreeNode left = invertTree(root.left);//翻转右子树TreeNode right= invertTree(root.right);}这里代码有个地方需要注意 ， 翻转完一棵树的左右子树 ， 还要交换它左右子树的引用位置 。
root.left = right; root.right = left;因此 ， leetcode这个递归经典题目的「终极解决代码」如下：
class Solution {public TreeNode invertTree(TreeNode root) {if(root==null || (root.left ==null}//翻转左子树TreeNode left = invertTree(root.left);//翻转右子树TreeNode right= invertTree(root.right);//左右子树交换位置~root.left = right;root.right = left;return root;}}拿终极解决代码去leetcode提交一下 ， 通过啦~
文章插图
递归存在的问题
- 递归调用层级太多 ， 导致栈溢出问题
- 递归重复计算 ， 导致效率低下
- 每一次函数调用在内存栈中分配空间 ， 而每个进程的栈容量是有限的 。
- 当递归调用的层级太多时 ， 就会超出栈的容量 ， 从而导致调用栈溢出 。
- 其实 ， 我们在前面小节也讨论了 ， 递归过程类似于出栈入栈 ， 如果递归次数过多 ， 栈的深度就需要越深 ， 最后栈容量真的不够咯
/** * 递归栈溢出测试 */public class RecursionTest {public static void main(String[] args) {sum(50000);}private static int sum(int n) {if (n <= 1) {return 1;}return sum(n - 1) + n;}}「运行结果:」Exception in thread "main" java.lang.StackOverflowError at recursion.RecursionTest.sum(RecursionTest.java:13)怎么解决这个栈溢出问题？首先需要「优化一下你的递归」 ， 真的需要递归调用这么多次嘛？如果真的需要 ， 先稍微「调大JVM的栈空间内存」 ， 如果还是不行 ， 那就需要弃用递归 ， 「优化为其他方案」咯~重复计算 ， 导致程序效率低下我们再来看一道经典的青蛙跳阶问题：一只青蛙一次可以跳上1级台阶 ， 也可以跳上2级台阶 。 求该青蛙跳上一个 n 级的台阶总共有多少种跳法 。
绝大多数读者朋友 ， 很容易就想到以下递归代码去解决：
class Solution {public int numWays(int n) {if (n == 0){return 1;}if(n <= 2){return n;}return numWays(n-1) + numWays(n-2);}}但是呢 ， 去leetcode提交一下 ， 就有问题啦 ， 超出时间限制了
文章插图为什么超时了呢？递归耗时在哪里呢？先画出「递归树」看看：
文章插图- 要计算原问题 f(10) ， 就需要先计算出子问题 f(9) 和 f(8)
- 然后要计算 f(9) ， 又要先算出子问题 f(8) 和 f(7) ， 以此类推 。
- 一直到 f(2) 和 f(1） ， 递归树才终止 。
推荐阅读
- 程序员为教师妻子开发应用：将iPhone变成文档摄像头
- 荣耀V40正式得到确认！参数配置也基本确定！售价或将是惊喜
- 九千元买的手机，最基本的功能都不好用，男子：还能干什么？
- 悔哭！一程序员误把7500个比特币当垃圾扔掉，估算约2.4亿美元
- 2.4亿美元打水漂！程序员小哥把7500个比特币当垃圾扔掉 硬盘找不回
- 程序员开发抢茅台脚本：2天就刷榜Github
- 为什么我喜欢C语言，却非常讨厌C++？一位国外程序员的回答
- 程序员怎么保护头发？雷军回应
- NVIDIA Broadcast体验 主播必备30系显卡
- 北美程序员Tinder翻车实录