一、數(shù)據(jù)結(jié)構(gòu)的存儲方式

數(shù)據(jù)結(jié)構(gòu)的存儲方式只有兩種：數(shù)組(順序存儲)和鏈表(鏈?zhǔn)酱鎯?。

這句話怎么理解，不是還有散列表、棧、隊(duì)列、堆、樹、圖等等各種數(shù)據(jù)結(jié)構(gòu)嗎?

我們分析問題，一定要有遞歸的思想，自頂向下，從抽象到具體。你上來就列出這么多，那些都屬于「上層建筑」，而數(shù)組和鏈表才是「結(jié)構(gòu)基礎(chǔ)」。因?yàn)槟切┒鄻踊臄?shù)據(jù)結(jié)構(gòu)，究其源頭，都是在鏈表或者數(shù)組上的特殊操作，API 不同而已。

比如說「隊(duì)列」、「?！惯@兩種數(shù)據(jù)結(jié)構(gòu)既可以使用鏈表也可以使用數(shù)組實(shí)現(xiàn)。用數(shù)組實(shí)現(xiàn)，就要處理擴(kuò)容縮容的問題;用鏈表實(shí)現(xiàn)，沒有這個(gè)問題，但需要更多的內(nèi)存空間存儲節(jié)點(diǎn)指針。

「圖」的兩種表示方法，鄰接表就是鏈表，鄰接矩陣就是二維數(shù)組。鄰接矩陣判斷連通性迅速，并可以進(jìn)行矩陣運(yùn)算解決一些問題，但是如果圖比較稀疏的話很耗費(fèi)空間。鄰接表比較節(jié)省空間，但是很多操作的效率上肯定比不過鄰接矩陣。

「散列表」就是通過散列函數(shù)把鍵映射到一個(gè)大數(shù)組里。而且對于解決散列沖突的方法，拉鏈法需要鏈表特性，操作簡單，但需要額外的空間存儲指針;線性探查法就需要數(shù)組特性，以便連續(xù)尋址，不需要指針的存儲空間，但操作稍微復(fù)雜些。

「樹」，用數(shù)組實(shí)現(xiàn)就是「堆」，因?yàn)椤付选故且粋€(gè)完全二叉樹，用數(shù)組存儲不需要節(jié)點(diǎn)指針，操作也比較簡單;用鏈表實(shí)現(xiàn)就是很常見的那種「樹」，因?yàn)椴灰欢ㄊ峭耆鏄?，所以不適合用數(shù)組存儲。為此，在這種鏈表「樹」結(jié)構(gòu)之上，又衍生出各種巧妙的設(shè)計(jì)，比如二叉搜索樹、AVL 樹、紅黑樹、區(qū)間樹、B 樹等等，以應(yīng)對不同的問題。

了解 Redis 數(shù)據(jù)庫的朋友可能也知道，Redis 提供列表、字符串、集合等等幾種常用數(shù)據(jù)結(jié)構(gòu)，但是對于每種數(shù)據(jù)結(jié)構(gòu)，底層的存儲方式都至少有兩種，以便于根據(jù)存儲數(shù)據(jù)的實(shí)際情況使用合適的存儲方式。

綜上，數(shù)據(jù)結(jié)構(gòu)種類很多，甚至你也可以發(fā)明自己的數(shù)據(jù)結(jié)構(gòu)，但是底層存儲無非數(shù)組或者鏈表，二者的優(yōu)缺點(diǎn)如下：

數(shù)組由于是緊湊連續(xù)存儲,可以隨機(jī)訪問，通過索引快速找到對應(yīng)元素，而且相對節(jié)約存儲空間。但正因?yàn)檫B續(xù)存儲，內(nèi)存空間必須一次性分配夠，所以說數(shù)組如果要擴(kuò)容，需要重新分配一塊更大的空間，再把數(shù)據(jù)全部復(fù)制過去，時(shí)間復(fù)雜度 O(N);而且你如果想在數(shù)組中間進(jìn)行插入和刪除，每次必須搬移后面的所有數(shù)據(jù)以保持連續(xù)，時(shí)間復(fù)雜度 O(N)。

鏈表因?yàn)樵夭贿B續(xù)，而是靠指針指向下一個(gè)元素的位置，所以不存在數(shù)組的擴(kuò)容問題;如果知道某一元素的前驅(qū)和后驅(qū)，操作指針即可刪除該元素或者插入新元素，時(shí)間復(fù)雜度 O(1)。但是正因?yàn)榇鎯臻g不連續(xù)，你無法根據(jù)一個(gè)索引算出對應(yīng)元素的地址，所以不能隨機(jī)訪問;而且由于每個(gè)元素必須存儲指向前后元素位置的指針，會消耗相對更多的儲存空間。

二、數(shù)據(jù)結(jié)構(gòu)的基本操作

對于任何數(shù)據(jù)結(jié)構(gòu)，其基本操作無非遍歷 + 訪問，再具體一點(diǎn)就是：增刪查改。

數(shù)據(jù)結(jié)構(gòu)種類很多，但它們存在的目的都是在不同的應(yīng)用場景，盡可能高效地增刪查改。話說這不就是數(shù)據(jù)結(jié)構(gòu)的使命么?

如何遍歷 + 訪問?我們?nèi)匀粡淖罡邔觼砜矗鞣N數(shù)據(jù)結(jié)構(gòu)的遍歷 + 訪問無非兩種形式：線性的和非線性的。

線性就是 for/while 迭代為代表，非線性就是遞歸為代表。再具體一步，無非以下幾種框架：

數(shù)組遍歷框架，典型的線性迭代結(jié)構(gòu)：

void traverse(int[] arr) {    for (int i = 0; i < arr.length; i++) {        // 迭代訪問 arr[i]    }} 

鏈表遍歷框架，兼具迭代和遞歸結(jié)構(gòu)：

/* 基本的單鏈表節(jié)點(diǎn) */class ListNode {    int val;    ListNode next;} 
void traverse(ListNode head) {    for (ListNode p = head; p != null; p = p.next) {        // 迭代訪問 p.val    }} 
void traverse(ListNode head) {    // 遞歸訪問 head.val    traverse(head.next);} 

二叉樹遍歷框架，典型的非線性遞歸遍歷結(jié)構(gòu)：

/* 基本的二叉樹節(jié)點(diǎn) */class TreeNode {    int val;    TreeNode left, right;} 
void traverse(TreeNode root) {    traverse(root.left);    traverse(root.right);} 

你看二叉樹的遞歸遍歷方式和鏈表的遞歸遍歷方式，相似不?再看看二叉樹結(jié)構(gòu)和單鏈表結(jié)構(gòu)，相似不?如果再多幾條叉，N 叉樹你會不會遍歷?

二叉樹框架可以擴(kuò)展為 N 叉樹的遍歷框架：

/* 基本的 N 叉樹節(jié)點(diǎn) */class TreeNode {    int val;    TreeNode[] children;} 
void traverse(TreeNode root) {    for (TreeNode child : root.children)        traverse(child);} 

N 叉樹的遍歷又可以擴(kuò)展為圖的遍歷，因?yàn)閳D就是好幾 N 叉棵樹的結(jié)合體。你說圖是可能出現(xiàn)環(huán)的?這個(gè)很好辦，用個(gè)布爾數(shù)組 visited 做標(biāo)記就行了，這里就不寫代碼了。

所謂框架，就是套路。不管增刪查改，這些代碼都是永遠(yuǎn)無法脫離的結(jié)構(gòu)，你可以把這個(gè)結(jié)構(gòu)作為大綱，根據(jù)具體問題在框架上添加代碼就行了，下面會具體舉例。

三、算法刷題指南

首先要明確的是，數(shù)據(jù)結(jié)構(gòu)是工具，算法是通過合適的工具解決特定問題的方法。也就是說，學(xué)習(xí)算法之前，最起碼得了解那些常用的數(shù)據(jù)結(jié)構(gòu)，了解它們的特性和缺陷。

那么該如何在 LeetCode 刷題呢?之前的文章算法學(xué)習(xí)之路寫過一些，什么按標(biāo)簽刷，堅(jiān)持下去云云?，F(xiàn)在距那篇文章已經(jīng)過去將近一年了，我不說那些不痛不癢的話，直接說具體的建議：

• 先刷二叉樹，先刷二叉樹，先刷二叉樹!

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

公眾號文章的閱讀數(shù)據(jù)顯示，大部分人對數(shù)據(jù)結(jié)構(gòu)相關(guān)的算法文章不感興趣，而是更關(guān)心動規(guī)回溯分治等等技巧。為什么要先刷二叉樹呢，因?yàn)槎鏄涫亲钊菀着囵B(yǎng)框架思維的，而且大部分算法技巧，本質(zhì)上都是樹的遍歷問題。

刷二叉樹看到題目沒思路?根據(jù)很多讀者的問題，其實(shí)大家不是沒思路，只是沒有理解我們說的「框架」是什么。不要小看這幾行破代碼，幾乎所有二叉樹的題目都是一套這個(gè)框架就出來了。

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

比如說我隨便拿幾道題的解法出來，不用管具體的代碼邏輯，只要看看框架在其中是如何發(fā)揮作用的就行。

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;} 

你看，這就是個(gè)后序遍歷嘛。

LeetCode 105 題，難度 Medium，讓你根據(jù)前序遍歷和中序遍歷的結(jié)果還原一棵二叉樹，很經(jīng)典的問題吧，主要代碼如下：

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;} 

不要看這個(gè)函數(shù)的參數(shù)很多，只是為了控制數(shù)組索引而已，本質(zhì)上該算法也就是一個(gè)前序遍歷。

LeetCode 99 題，難度 Hard，恢復(fù)一棵 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);} 

這不就是個(gè)中序遍歷嘛，對于一棵 BST 中序遍歷意味著什么，應(yīng)該不需要解釋了吧。

你看，Hard 難度的題目不過如此，而且還這么有規(guī)律可循，只要把框架寫出來，然后往相應(yīng)的位置加?xùn)|西就行了，這不就是思路嗎。

對于一個(gè)理解二叉樹的人來說，刷一道二叉樹的題目花不了多長時(shí)間。那么如果你對刷題無從下手或者有畏懼心理，不妨從二叉樹下手，前 10 道也許有點(diǎn)難受;結(jié)合框架再做 20 道，也許你就有點(diǎn)自己的理解了;刷完整個(gè)專題，再去做什么回溯動規(guī)分治專題，你就會發(fā)現(xiàn)只要涉及遞歸的問題，都是樹的問題。

再舉例吧，說幾道我們之前文章寫過的問題。

動態(tài)規(guī)劃詳解說過湊零錢問題，暴力解法就是遍歷一棵 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) 

這么多代碼看不懂咋辦?直接提取出框架，就能看出核心思路了：

# 不過是一個(gè) N 叉樹的遍歷問題而已def dp(n):    for coin in coins:        dp(n - coin) 

其實(shí)很多動態(tài)規(guī)劃問題就是在遍歷一棵樹，你如果對樹的遍歷操作爛熟于心，起碼知道怎么把思路轉(zhuǎn)化成代碼，也知道如何提取別人解法的核心思路。

再看看回溯算法，前文回溯算法詳解干脆直接說了，回溯算法就是個(gè) N 叉樹的前后序遍歷問題，沒有例外。

比如 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]);        // 進(jìn)入下一層決策樹        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 叉樹的遍歷框架，找出來了把～你說，樹這種結(jié)構(gòu)重不重要?

綜上，對于畏懼算法的朋友來說，可以先刷樹的相關(guān)題目，試著從框架上看問題，而不要糾結(jié)于細(xì)節(jié)問題。

糾結(jié)細(xì)節(jié)問題，就比如糾結(jié) i 到底應(yīng)該加到 n 還是加到 n - 1，這個(gè)數(shù)組的大小到底應(yīng)該開 n 還是 n + 1 ?

從框架上看問題，就是像我們這樣基于框架進(jìn)行抽取和擴(kuò)展，既可以在看別人解法時(shí)快速理解核心邏輯，也有助于找到我們自己寫解法時(shí)的思路方向。

當(dāng)然，如果細(xì)節(jié)出錯(cuò)，你得不到正確的答案，但是只要有框架，你再錯(cuò)也錯(cuò)不到哪去，因?yàn)槟愕姆较蚴菍Φ摹?/p>

但是，你要是心中沒有框架，那么你根本無法解題，給了你答案，你也不會發(fā)現(xiàn)這就是個(gè)樹的遍歷問題。

這種思維是很重要的，動態(tài)規(guī)劃詳解中總結(jié)的找狀態(tài)轉(zhuǎn)移方程的幾步流程，有時(shí)候按照流程寫出解法，說實(shí)話我自己都不知道為啥是對的，反正它就是對了。。。

這就是框架的力量，能夠保證你在快睡著的時(shí)候，依然能寫出正確的程序;就算你啥都不會，都能比別人高一個(gè)級別。

四、總結(jié)幾句

數(shù)據(jù)結(jié)構(gòu)的基本存儲方式就是鏈?zhǔn)胶晚樞騼煞N，基本操作就是增刪查改，遍歷方式無非迭代和遞歸。

刷算法題建議從「樹」分類開始刷，結(jié)合框架思維，把這幾十道題刷完，對于樹結(jié)構(gòu)的理解應(yīng)該就到位了。這時(shí)候去看回溯、動規(guī)、分治等算法專題，對思路的理解可能會更加深刻一些。