算法刷题指南，来自GitHub 68.8k star的硬核算法教程

很多朋友害怕算法，其实大可不必，算法题无非就那几个套路，一旦掌握，就会觉得算法实在是太朴实无华且枯燥了！
本文选自硬核算法教程《labuladong的算法小抄》，带你学习套路，把握各类算法问题的共性！
数据结构是工具，算法是通过合适的工具解决特定问题的方法。对于任何数据结构，其基本操作无非遍历 + 访问，再具体一点就是：增、删、查、改。
那么该如何在力扣刷题呢？很多文章都会告诉你“按标签刷”“坚持下去”等。不说这些不痛不痒的话，直接给具体的建议。
先刷二叉树
先刷二叉树
！！先刷二叉树！！
这是我刷题一年的亲身体会，下图是 2019 年 10 月的提交截图：

据我观察，大部分人对与数据结构相关的算法文章不感兴趣，而是更关心动态规划、回溯、分治等技巧。这是不对的，这些常考算法技巧在《labuladong的算法小抄》中都会有所涉及，到时候你就会发现，它们看起来高大上，但本质上就是一个多叉树遍历的问题，配合算法框架，并没有多难。
为什么要先刷二叉树呢？

因为二叉树是最容易培养框架思维的，而且大部分常考算法本质上都是树的遍历问题。
刷二叉树时看到题目没思路？

其实大家不是没思路，只是没有理解“框架”是什么。不要小看下面这几行代码，几乎所有二叉树的题目一套用这个框架就都出来了。

void traverse(TreeNode root) {
    // 前序遍历
    traverse(root.left);
    // 中序遍历
    traverse(root.right);
    // 后序遍历
}

比如随便拿几道题的解法代码出来，这里不用管具体的代码逻辑，只看看框架在其中是如何发挥作用的。
LeetCode 124 题，难度为 Hard，求二叉树中最大路径和，主要代码如下：

int ans = INT_MIN;
int oneSideMax(TreeNode* root) {
    if (root == nullptr) return 0;

    int left = max(0, oneSideMax(root->left));
    int right = max(0, oneSideMax(root->right));

    /**** 后序遍历 ****/
    ans = max(ans, left + right + root->val);
    return max(left, right) + root->val;
    /****************/
}

你看，这不就是后序遍历嘛。
那为什么是后序呢？题目要求最大路径和，对于一个二叉树节点，是不是先计算左子树和右子树的最大路径和，然后加上自己的值，这样就得出新的最大路径和了？所以说这里就要使用后续遍历框架。
LeetCode 105 题，难度为 Medi um，要求根据前序遍历和中序遍历的结果还原一棵二叉树，这是很经典的问题，主要代码如下：

 TreeNode buildTree(int[] preorder, int preStart, int preEnd, 
     int[] inorder, int inStart, int inEnd, Map<Integer, Integer> inMap) {

     if(preStart > preEnd || inStart > inEnd) return null;

     /**** 前序遍历 ****/
     TreeNode root = new TreeNode(preorder[preStart]);
     int inRoot = inMap.get(root.val);
     int numsLeft = inRoot - inStart;
    /****************/

    root.left = buildTree(preorder, preStart + 1, preStart + numsLeft, 
                          inorder, inStart, inRoot - 1, inMap);
    root.right = buildTree(preorder, preStart + numsLeft + 1, preEnd, 
                         inorder, inRoot + 1, inEnd, inMap);
    return root;
}

不要看这个函数的参数很多，它们只是为了控制数组索引而已，本质上该算法就是一个前序遍历算法。
LeetCode 99 题，难度为 Hard，要求恢复一棵 BST（完全二叉树），主要代码如下：

 void traverse(TreeNode* node) {
     if (!node) return;

     traverse(node->left);

     /****中序遍历 ****/
     if (node->val < prev->val) {
         s = (s == NULL) ? prev : s;
         t = node;
    }
    prev = node;
    /****************/

   traverse(node->right);
   }

这不就是中序遍历嘛，对于一棵 BST，中序遍历意味着什么，应该不需要解释了吧。
你看，Hard 难度的题目不过如此，而且还这么有规律可循，只要把框架写出来，然后往相应的位置加内容就行了，这不就是思路嘛！
对于一个理解二叉树的人来说，刷一道二叉树的题目花不了多长时间。那么如果你对刷题无从下手或者有畏惧心理，不妨从二叉树下手，前 10 道也许有点难受；结合框架再做 20 道题，也许你就有点自己的理解了；刷完整个专题，再去做什么回溯、动态规化、分治专题，你就会发现只要涉及递归的问题，基本上都是树的问题。
▽▽▽
再举些例子吧。
在《labuladong的算法小抄》“动态规划解题套路框架”章节中，会讲到凑零钱问题，暴力解法就是遍历一棵 N 叉树：

 def coinChange(coins: List[int], amount: int):

     def dp(n):
         if n == 0: return 0
         if n < 0: return -1

         res = float('INF')
         for coin in coins:
             subproblem = dp(n - coin)
            # 子问题无解，跳过
            if subproblem == -1: continue
            res = min(res, 1 + subproblem)
        return res if res != float('INF') else -1

    return dp(amount)

这么多代码看不懂怎么办？直接提取框架，这样就能看出核心思路了，这就是刚才说到的遍历 N 叉树的框架：

def dp(n):
    for coin in coins:
        dp(n - coin)

其实很多动态规划问题就是在遍历一棵树，你如果对树的遍历操作烂熟于心，那么起码知道怎么把思路转化成代码，也知道如何提取别人解法的核心思路。
再看看回溯算法，在《labuladong的算法小抄》“回溯算法解题套路框架”中会直接告诉你，回溯算法就是一个 N 叉树的前序 + 后序遍历问题，没有例外。比如，排列组合问题、经典的回溯问题，主要代码如下：

 void backtrack(int[] nums, LinkedList<Integer> track) {
     if (track.size() == nums.length) {
         res.add(new LinkedList(track));
         return;
     }

     for (int i = 0; i < nums.length; i++) {
         if (track.contains(nums[i]))
             continue;
        track.add(nums[i]);
        // 进入下一层决策树
        backtrack(nums, track);
        track.removeLast();
    }

/* 提取 N叉树遍历框架 */
void backtrack(int[] nums, LinkedList<Integer> track) {
    for (int i = 0; i < nums.length; i++) {
        backtrack(nums, track);
}

N 叉树的遍历框架，找出来了吧。你说，树这种结构重不重要？
综上所述，对于畏惧算法或者刷题很多但依然感觉不得要领的朋友来说，可以先刷树的相关题目，试着从框架看问题，而不要纠结于细节。

所谓纠结细节，就比如纠结 i 到底应该加到 n 还是加到 n - 1 ，这个数组的大小到底应该开成 n 还是 n + 1 ？
从框架看问题，就是像我们这样基于框架进行抽取和扩展，既可以在看别人解法时快速理解核心逻辑，也有助于我们找到自己写解法时的思路方向。
当然，如果细节出错，你将得不到正确的答案，但是只要有框架，再错也错不到哪去，因为你的方向是对的。但是，你要是心中没有框架，那么根本无法解题，给你答案，也不能意识到这就是树的遍历问题。
框架思维是很重要的，有时候按照流程写出解法，说实话我自己都不知道为啥是对的，反正它就是对了……
这就是框架的力量，能够保证你在思路不那么清晰的时候，依然写出正确的程序。
—— ——

最后我们总结一下，刷算法题建议从“树”分类开始刷，结合框架思维，把几十道题刷完，对于树结构的理解应该就到位了。这时候去看回溯、动态规划、分治等算法专题，对思路的理解可能会更加深刻一些。
在思考问题的过程中，少纠结细节，不要热衷于炫技；希望读者多从框架看问题，多学习套路，把握各类算法问题的共性，《labuladong的算法小抄》将会为你提供这方面的帮助。

图书推荐

▊《labuladong的算法小抄》
付东来（@labuladong）著