小白一路走来，连续刷题三年，谈谈我的算法学习经验( 二 ) _二叉树

文章插图
这本书是牛客网的左程云写的，这本书重在带你刷题，每道题的解法也是讲的挺详细的，而且，这本书是一个专题一个专题带你刷题的，从栈和队列、链表、二叉树、递归与动态规划、字符串等等。我之前的链表打卡就是从这里找的。大家可以按照自己的弱点挑着刷。对了，代码是采用 Java 实现的，不过你会 C 语言的话，一样能看懂。真心不过，递归和动态规划里面好几道题都命中这次春招笔试了，当然，类似而已。然而，那时我还没有去看这本书动态相关的专题。推荐给大家。做个补充：这些书籍我都有保存了电子版的，不过百度云发出来经常会链接失效，我不好及时更新，不过你可以持续关注我，明天我会在微头条发这些电子书，当然，你也可以私信我勒。
说实话，我那一学期的时间几乎都花在数据结构与算法上，但刷的题很少，只是书本上的一些例题。所以当我把这些基本的过一遍之后，再去一些网站刷题依旧非常菜。
所以你们千万别指望以为自己把这些思想学完之后刷题会很牛，只有多刷题，只有多动手实践，你的灵敏度才会提高起来。
总结下：
提高数据结构与算法没啥捷径，最好的捷径就是多刷题。但是，刷题的前提是你要先学会一些基本的数据结构与算法思想。
2、AC不是目的，我们要追求完美
如何刷题？如何对待一道算法题？
我觉得，在做题的时候，一定要追求完美，千万不要把一道题做出来之后，提交通过，然后就赶紧下一道。我认为这意义不大，因为一道题的解法太多了，有些解法态粗糙了，我们应该要寻找最优的方法。
算法能力的提升和做题的数量是有一定的关系，但并不是线性关系。也就是说，在做题的时候，要力求一题多解，如果自己实在想不出来其他办法了，可以去看看别人是怎么做的，千万不要觉得模仿别人的做法是件丢人的事。
我做题的时候，我一看到一道题，可能第一想法就是用很粗糙的方式做，因为很多题采用暴力法都会很容易做，就是时间复杂度很高。之后，我就会慢慢思考，看看有没其他方法来降低时间复杂度或空间复杂度。最后，我会去看一下别人的做法，当然，并不是每道题都会这样执行。
衡量一道算法题的好坏无非就是时间复杂度和空间复杂度，所以我们要力求完美，就要把这两个降到最低，令他们相辅相成。
我举道例题吧：
问题：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法？
这道题我在以前的分章分析过，不懂的可以先看下之前写的：递归与动态规划---基础篇1
方法1：：暴力递归
这道题不难，或许你会采取下面的做法：
public static int solve(int n){ if(n == 1 || n == 2){ return n; }else if(n <= 0){ return 0; }else{ return solve(n-1) + solve(n-2); }}
这种做法的时间复杂度很高，指数级别了。但是如果你提交之后侥幸通过了，然后你就接着下一道题了，那么你就要好好想想了。
方法二：空间换时间
力求完美，我们可以考虑用空间换时间：这道题如何你去仔细想一想，会发现有很多是重复执行了。所以可以采取下面的方法：
//用一个HashMap来保存已经计算过的状态static Map map = new HashMap();public static int solve(int n){ if(n <= 0)return 0; else if(n <= 2){ return n; }else{//是否计算过 if(map.containsKey(n)){ return map.get(n); }else{ int m = solve(n-1) + solve(n-2); map.put(n, m); return m; } }}
这样，可以大大缩短时间。也就是说，当一道题你做了之后，发现时间复杂度很高，那么可以考虑下，是否有更好的方法，是否可以用空间换时间。
方法三：斐波那契数列
实际上，我们可以把空间复杂度弄的更小，不需要HashMap来保存状态：
public static int solve(int n){ if(n <= 0) return 0; if(n <= 2){ return n; } int f1 = 0; int f2 = 1; int sum = 0; for(int i = 1; i<= n; i++){ sum = f1 + f2; f1 = f2; f2 = sum; } return sum;}
我弄这道题给你们看，并不是在教你们这道题怎么做，而是有以下目的：
1、在刷题的时候，我们要力求完美。
2、我想不到这些方法啊，怎么办？那么你就可以去看别人的做法，之后，遇到类似的题，你就会更有思路，更知道往哪个方向想。
3、可以从简单暴力入手做一道题，在考虑空间与时间之间的衡量，一点点去优化。
3、挑战自己，跳出舒适区
什么叫舒适区？在刷题的时候，可能有一类题是你比较懂的，你每次一看就有思路，然后半个小时就撸好代码，提交代码，然后通过了，然后，哇，又多刷了一道题，心里很舒服。