很多朋友害怕演算法，其實大可不必，演算法題無非就那幾個套路，一旦掌握，就會覺得演算法實在是太樸實無華且枯燥了！

本文選自硬核演算法教程《labuladong的演算法小抄》，帶你學習套路，把握各類演算法問題的共性！

資料結構是工具，演算法是透過合適的工具解決特定問題的方法。對於任何資料結構，其基本操作無非遍歷 + 訪問，再具體一點就是：增、刪、查、改。

那麼該如何在力扣刷題呢？很多文章都會告訴你“按標籤刷”“堅持下去”等。不說這些不痛不癢的話，直接給具體的建議。

先刷二叉樹

先刷二叉樹

！！先刷二叉樹！！

這是我刷題一年的親身體會，下圖是 2019 年 10 月的提交截圖：

據我觀察，大部分人對與資料結構相關的演算法文章不感興趣，而是更關心動態規劃、回溯、分治等技巧。這是不對的，這些常考演算法技巧在《labuladong的演算法小抄》中都會有所涉及，到時候你就會發現，它們看起來高大上，但本質上就是一個多叉樹遍歷的問題，配合演算法框架，並沒有多難。

為什麼要先刷二叉樹呢？

因為二叉樹是最容易培養框架思維的，而且大部分常考演算法本質上都是樹的遍歷問題。

刷二叉樹時看到題目沒思路？

其實大家不是沒思路，只是沒有理解“框架”是什麼。不要小看下面這幾行程式碼，幾乎所有二叉樹的題目一套用這個框架就都出來了。

1void traverse(TreeNode root) {2    // 前序遍歷3    traverse(root.left);4    // 中序遍歷5    traverse(root.right);6    // 後序遍歷7}

比如隨便拿幾道題的解法程式碼出來，這裡不用管具體的程式碼邏輯，只看看框架在其中是如何發揮作用的。

LeetCode 124 題 ，難度為 Hard，求二叉樹中最大路徑和，主要程式碼如下：

 1int ans = INT_MIN; 2int oneSideMax(TreeNode* root) { 3    if (root == nullptr) return 0; 4 5    int left = max(0, oneSideMax(root->left)); 6    int right = max(0, oneSideMax(root->right)); 7 8    /**** 後序遍歷 ****/ 9    ans = max(ans, left + right + root->val);10    return max(left, right) + root->val;11    /****************/12}

你看，這不就是後序遍歷嘛。

那為什麼是後序呢？題目要求最大路徑和，對於一個二叉樹節點，是不是先計算左子樹和右子樹的最大路徑和，然後加上自己的值，這樣就得出新的最大路徑和了？所以說這裡就要使用後續遍歷框架。

LeetCode 105 題 ，難度為 Medi um，要求根據前序遍歷和中序遍歷的結果還原一棵二叉樹，這是很經典的問題，主要程式碼如下：

 1TreeNode buildTree(int[] preorder, int preStart, int preEnd,  2    int[] inorder, int inStart, int inEnd, Map<Integer, Integer> inMap) { 3 4    if(preStart > preEnd || inStart > inEnd) return null; 5 6    /**** 前序遍歷 ****/ 7    TreeNode root = new TreeNode(preorder[preStart]); 8    int inRoot = inMap.get(root.val); 9    int numsLeft = inRoot - inStart;10    /****************/1112    root.left = buildTree(preorder, preStart + 1, preStart + numsLeft, 13                          inorder, inStart, inRoot - 1, inMap);14    root.right = buildTree(preorder, preStart + numsLeft + 1, preEnd, 15                          inorder, inRoot + 1, inEnd, inMap);16    return root;17}

不要看這個函式的引數很多，它們只是為了控制陣列索引而已，本質上該演算法就是一個前序遍歷演算法。

LeetCode 99 題 ，難度為 Hard，要求恢復一棵 BST（完全二叉樹），主要程式碼如下：

 1void traverse(TreeNode* node) { 2    if (!node) return; 3 4    traverse(node->left); 5 6    /****中序遍歷 ****/ 7    if (node->val < prev->val) { 8        s = (s == NULL) ? prev : s; 9        t = node;10    }11    prev = node;12    /****************/1314    traverse(node->right);15}

這不就是中序遍歷嘛，對於一棵 BST，中序遍歷意味著什麼，應該不需要解釋了吧。

你看，Hard 難度的題目不過如此，而且還這麼有規律可循，只要把框架寫出來，然後往相應的位置加內容就行了，這不就是思路嘛！

對於一個理解二叉樹的人來說，刷一道二叉樹的題目花不了多長時間。那麼如果你對刷題無從下手或者有畏懼心理，不妨從二叉樹下手，前 10 道也許有點難受；結合框架再做 20 道題，也許你就有點自己的理解了；刷完整個專題，再去做什麼回溯、動態規化、分治專題，你就會發現只要涉及遞迴的問題，基本上都是樹的問題。

▽▽▽

再舉些例子吧。

在《labuladong的演算法小抄》“動態規劃解題套路框架”章節中，會講到湊零錢問題，暴力解法就是遍歷一棵 N 叉樹：

 1def coinChange(coins: List[int], amount: int): 2 3    def dp(n): 4        if n == 0: return 0 5        if n < 0: return -1 6 7        res = float('INF') 8        for coin in coins: 9            subproblem = dp(n - coin)10            # 子問題無解，跳過11            if subproblem == -1: continue12            res = min(res, 1 + subproblem)13        return res if res != float('INF') else -11415    return dp(amount)

這麼多程式碼看不懂怎麼辦？直接提取框架，這樣就能看出核心思路了，這就是剛才說到的遍歷 N 叉樹的框架：

1def dp(n):2    for coin in coins:3        dp(n - coin)

其實很多動態規劃問題就是在遍歷一棵樹，你如果對樹的遍歷操作爛熟於心，那麼起碼知道怎麼把思路轉化成程式碼，也知道如何提取別人解法的核心思路。

再看看回溯演算法，在《labuladong的演算法小抄》“回溯演算法解題套路框架”中會直接告訴你，回溯演算法就是一個 N 叉樹的前序 + 後序遍歷問題，沒有例外。比如，排列組合問題、經典的回溯問題，主要程式碼如下：

 1void backtrack(int[] nums, LinkedList<Integer> track) { 2    if (track.size() == nums.length) { 3        res.add(new LinkedList(track)); 4        return; 5    } 6 7    for (int i = 0; i < nums.length; i++) { 8        if (track.contains(nums[i])) 9            continue;10        track.add(nums[i]);11        // 進入下一層決策樹12        backtrack(nums, track);13        track.removeLast();14    }1516/* 提取 N叉樹遍歷框架 */17void backtrack(int[] nums, LinkedList<Integer> track) {18    for (int i = 0; i < nums.length; i++) {19        backtrack(nums, track);20}

N 叉樹的遍歷框架，找出來了吧。你說，樹這種結構重不重要？

綜上所述，對於畏懼演算法或者刷題很多但依然感覺不得要領的朋友來說，可以先刷樹的相關題目，試著從框架看問題，而不要糾結於細節。

所謂糾結細節，就比如糾結 i 到底應該加到 n 還是加到 n - 1 ，這個陣列的大小到底應該開成 n 還是 n + 1 ？

從框架看問題，就是像我們這樣基於框架進行抽取和擴充套件，既可以在看別人解法時快速理解核心邏輯，也有助於我們找到自己寫解法時的思路方向。

當然，如果細節出錯，你將得不到正確的答案，但是隻要有框架，再錯也錯不到哪去，因為你的方向是對的。但是，你要是心中沒有框架，那麼根本無法解題，給你答案，也不能意識到這就是樹的遍歷問題。

框架思維是很重要的，有時候按照流程寫出解法，說實話我自己都不知道為啥是對的，反正它就是對了……

這就是框架的力量，能夠保證你在思路不那麼清晰的時候，依然寫出正確的程式。

—— ——

最後我們總結一下，刷演算法題建議從“樹”分類開始刷，結合框架思維，把幾十道題刷完，對於樹結構的理解應該就到位了。這時候去看回溯、動態規劃、分治等演算法專題，對思路的理解可能會更加深刻一些。

在思考問題的過程中，少糾結細節，不要熱衷於炫技；希望讀者多從框架看問題，多學習套路，把握各類演算法問題的共性，《labuladong的演算法小抄》將會為你提供這方面的幫助。

圖書推薦

▊《labuladong的演算法小抄》

付東來（@labuladong） 著

GitHub 68.8k star的硬核演算法教程labuladong帶你挑戰力扣演算法題挑戰BAT等大廠Offer

本書專攻演算法刷題，訓練演算法思維，應對演算法筆試。注重用套路和框架思維解決問題，以不變應萬變。