一衩婚、數(shù)據(jù)結(jié)構(gòu)的存儲方式
數(shù)據(jù)結(jié)構(gòu)的存儲方式只有兩種：數(shù)組（順序存儲）和鏈表（鏈式存儲）
不是還有散列表、棧效斑、隊列非春、堆、樹缓屠、圖等數(shù)據(jù)結(jié)構(gòu)嗎奇昙？
這些都是術(shù)（上層建筑），而數(shù)組和鏈表才是道（結(jié)構(gòu)基礎(chǔ)）藏研。那些多樣化的數(shù)據(jù)結(jié)構(gòu)敬矩，究其源頭，都是在鏈表或數(shù)組上的特殊操作蠢挡，API不同而已弧岳。
比如隊列、棧這兩種數(shù)據(jù)結(jié)構(gòu)既可以用鏈表也可以用數(shù)組實現(xiàn)业踏。用數(shù)組實現(xiàn)禽炬，就要處理擴容縮容問題；用鏈表實現(xiàn)勤家，沒有這個問題腹尖，但需要更多的內(nèi)存空間存儲節(jié)點指針。
〔 圖〕的兩種表示方式伐脖，鄰接表就是鏈表热幔，鄰接矩陣就是二維數(shù)組。鄰接矩陣判斷連通性迅速讼庇，并可以進行矩陣運算解決一些問題绎巨，但是如果圖比較稀疏的話很耗費空間。鄰接表比較節(jié)省空間蠕啄，但很多操作的效率上肯定比不過鄰接矩陣场勤。
〔散列表〕就是通過散列函數(shù)把鍵映射到一個大數(shù)組里。而且對于解決散列沖突的方法歼跟，拉鏈法需要鏈表特性和媳，操作簡單，但需要額外空間存儲指針哈街；線性探查法就需要數(shù)組特性留瞳，以便連續(xù)尋址，不需要指針的存儲空間骚秦，但操作稍微復雜些撼港。（注：解決沖突常用方法有拉鏈法和開放地址檢測法（包括線性探測坪它、平方探測、雙散列）帝牡，不常用的有再散列往毡。這里沒有看出拉鏈法相比其他方法的簡單之處？另靶溜，散列表本身即數(shù)組特性开瞭，拉鏈法加入了鏈表特性）
〔樹〕，用數(shù)組實現(xiàn)就是〔堆〕罩息，因為〔堆〕是一個完全二叉樹嗤详，用數(shù)組存儲不需要節(jié)點指針，操作也比較簡單（really瓷炮？）葱色；用鏈表實現(xiàn)就是很常見的那種〔樹〕，不一定是完全二叉樹（則不適合數(shù)組存儲）娘香。為此苍狰，在這種鏈表〔樹〕結(jié)構(gòu)之上，又衍生出各種巧妙的設(shè)計烘绽，比如二叉搜索樹淋昭、AVL樹、紅黑樹安接、區(qū)間樹翔忽、B樹等等，以對應(yīng)不同的問題
Redis提供列表盏檐、字符串歇式、集合等幾種常用的數(shù)據(jù)結(jié)構(gòu)，但對于每種數(shù)據(jù)結(jié)構(gòu)胡野，底層的存儲方式都至少有兩種贬丛，以便根據(jù)存儲數(shù)據(jù)的實際情況使用合適的存儲方式。
數(shù)組由于是緊湊連續(xù)存儲给涕，可以隨機訪問，通過索引快速找到對應(yīng)元素额获，而且的相對節(jié)約存儲空間够庙。但正因為連續(xù)存儲，內(nèi)存空間必須一次性分配夠抄邀，數(shù)組如果要擴容需要分配一塊更大的空間耘眨，再把數(shù)據(jù)全部復制過去，時間復雜度O(N)境肾；在數(shù)組中間插入和刪除每次也必須搬移后面的所有數(shù)據(jù)以保持連續(xù)剔难，時間復雜度O(N)胆屿。
鏈表因為元素不連續(xù)，而是靠指針指向下一個元素的位置偶宫，所以不存在數(shù)組的擴容問題非迹；如果知道某一元素的前驅(qū)和后繼，操作指針即可刪除該元素或者插入新元素纯趋，時間復雜度O(1)憎兽。但正是因為存儲空間不連續(xù)，你無法根據(jù)一個索引算出對應(yīng)元素的地址吵冒，所以不能隨機訪問纯命；而且由于每個元素必須存儲指向（前）后元素位置的指針，會消耗更多的存儲空間痹栖。
二亿汞、數(shù)據(jù)結(jié)構(gòu)的基本操作
對于任何數(shù)據(jù)結(jié)構(gòu)，基本操作無非遍歷+訪問揪阿，再具體一點就是：增刪查改疗我。各種數(shù)據(jù)結(jié)構(gòu)的遍歷+訪問無非兩種形式：線性的和非線性的。
線性就是for/while迭代為代表图甜，非線性就是遞歸為代表碍粥。再具體一點無非以下幾種框架：
1. 數(shù)組遍歷框架，典型的線性迭代結(jié)構(gòu)
2. 鏈表遍歷框架黑毅，兼具迭代和遞歸結(jié)構(gòu)：
class ListNode{
? ? int val;
? ? ListNode next;
}
void traverse(ListNode head) {
? ? // 迭代訪問
? ? for(ListNode p ＝ head; p !＝ null; p ＝ p.next){
? ? }
? ? // 遞歸訪問
? ? while(head !＝ null)
? ? ? ? traverse(head.next);
}
3.二叉樹遍歷框架嚼摩，典型的非線性遞歸遍歷結(jié)構(gòu)：
class TreeNode {
? ? int val;
? ? TreeNode left, right;
}
void traverse(TreeNode root) {
? ? if(root ＝＝ null) return;
? ? // 前序
? ? root.val;
? ? traverse(root.left);
? ? traverse(root.right);
}
二叉樹和的遞歸遍歷方式其實和鏈表的遞歸遍歷方式很相似！它們的結(jié)構(gòu)也很相似矿瘦！二叉樹擴展到多叉樹也很類似：
class TreeNode {
? ? int val;
? ? TreeNode[] children;
}
void traverse(TreeNode root){
? ? // 前序
? ? root.val;
? ? for(TreeNode child : root.children)
? ? ? ? traverse(child);
}
N叉樹的遍歷又可以擴展為圖的遍歷枕面，因為圖就是好幾棵N叉樹的結(jié)合體。而對于有環(huán)圖缚去，用個布爾數(shù)組visited做標記就行了潮秘。
三、算法刷題指南
先刷二叉樹
因為二叉樹最容易培養(yǎng)框架思維易结，且大部分算法技巧本質(zhì)上都是樹的遍歷問題枕荞。
leetcode124題，難度hard搞动，求二叉樹中最大路徑和躏精，主要代碼如下：
int ans ＝ INT_MIN;
int oneSideMax(TreeNode root) {
? ? if(root ＝＝ null) 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題鹦肿，難度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;
}
不要看這個函數(shù)參數(shù)很多瞭吃，只是為了控制數(shù)組索引而已碌嘀，本質(zhì)上也就是一個前序遍歷。
leetcode 99題歪架，難度hard股冗，恢復一棵BST，主要代碼如下：
void traverse(TreeNode node) {
? ? if(node ＝＝ null) return;
? ? traverse(node.left);
? ? if(node.val ＜ pre.val) {
? ? ? ? s ＝ (s ＝＝ null) ? prev : s;
? ? ? ? t ＝ node;
? ? }
? ? prev ＝ node;
? ? traverse(node.right);
}
這是一個中序遍歷牡拇，一棵BST的中序遍歷意味著值的升序排列魁瞪。
刷完整個二叉樹專題，再回去做回溯動規(guī)分治專題惠呼，會發(fā)現(xiàn)只要涉及遞歸的問題导俘，都是樹的問題。
很多動態(tài)規(guī)劃問題就是在遍歷一棵樹剔蹋，你如果對樹的遍歷操作爛熟于心旅薄，起碼知道怎么把思路轉(zhuǎn)化成代碼，也知道如何提取別人解法的和新思路泣崩。
回溯算法就是個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]);
? ? ? ? // 進入下一層決策樹
? ? ? ? backtrack(nums, track);
? ? ? ? track.removeLast();
? ? }
}
// 提取出N叉樹遍歷框架
void backtrack(int[] nums, LinkedList<Integer> track) {
? ? for(int i ＝ 0; i ＜nums.length; i++) {
? ? ? ? backtrack(nums, track);
? ? }
}
框架思維很重要凯沪，動態(tài)規(guī)劃講解中總結(jié)的找狀態(tài)轉(zhuǎn)移方程的幾步流程，有時候按照流程寫出解法买优，莫名其妙就對了妨马。這就是框架的力量，能保證你在快睡著的時候杀赢，依然能寫出正確的程序烘跺。
四、總結(jié)
數(shù)據(jù)結(jié)構(gòu)的基本存儲方式就是鏈式和順序兩種脂崔，基本操作就是增刪改查滤淳，遍歷方式無非迭代和遞歸。
刷算法題建議從〔樹〕分類開始砌左，結(jié)合框架思維脖咐，把這幾十道題刷完，對于樹的理解應(yīng)該就到位了汇歹。這時候去看回溯屁擅、動態(tài)規(guī)劃、分治等算法專題秤朗，對思路的理解可能會更加深刻一些。
