共计 5660 个字符，预计需要花费 15 分钟才能阅读完成。
———–
告诉：如果本站对你学习算法有帮忙，请珍藏网址，并举荐给你的敌人 。因为 labuladong 的算法套路太火，很多人间接拿我的 GitHub 文章去开付费专栏，价格还不便宜。我这收费写给你看， 多宣传原创作者是你惟一能做的，谁也不心愿劣币驱赶良币对吧？
这是良久之前的一篇文章「学习数据结构和算法的框架思维」的修订版。之前那篇文章收到宽泛好评，没看过也没关系，这篇文章会涵盖之前的所有内容，并且会举很多代码的实例，教你如何应用框架思维。
首先，这里讲的都是一般的数据结构，咱不是搞算法比赛的，野路子出世，我只会解决惯例的问题。另外，以下是我集体的教训的总结，没有哪本算法书会写这些货色，所以请读者试着了解我的角度，别纠结于细节问题，因为这篇文章就是心愿对数据结构和算法建设一个框架性的意识。
从整体到细节，自顶向下，从形象到具体的框架思维是通用的，不只是学习数据结构和算法，学习其余任何常识都是高效的。
一、数据结构的存储形式
数据结构的存储形式只有两种：数组（顺序存储）和链表（链式存储）。
这句话怎么了解，不是还有散列表、栈、队列、堆、树、图等等各种数据结构吗？
咱们剖析问题，肯定要有递归的思维，自顶向下，从形象到具体。你上来就列出这么多，那些都属于「上层建筑」，而数组和链表才是「构造根底」。因为那些多样化的数据结构，究其源头，都是在链表或者数组上的非凡操作，API 不同而已。
比如说「队列」、「栈」这两种数据结构既能够应用链表也能够应用数组实现。用数组实现，就要解决扩容缩容的问题；用链表实现，没有这个问题，但须要更多的内存空间存储节点指针。
「图」的两种示意办法，邻接表就是链表，邻接矩阵就是二维数组。邻接矩阵判断连通性迅速，并能够进行矩阵运算解决一些问题，然而如果图比拟稠密的话很消耗空间。邻接表比拟节俭空间，然而很多操作的效率上必定比不过邻接矩阵。
「散列表」就是通过散列函数把键映射到一个大数组里。而且对于解决散列抵触的办法，拉链法须要链表个性，操作简略，但须要额定的空间存储指针；线性探查法就须要数组个性，以便间断寻址，不须要指针的存储空间，但操作略微简单些。
「树」，用数组实现就是「堆」，因为「堆」是一个齐全二叉树，用数组存储不须要节点指针，操作也比较简单；用链表实现就是很常见的那种「树」，因为不肯定是齐全二叉树，所以不适宜用数组存储。为此，在这种链表「树」构造之上，又衍生出各种奇妙的设计，比方二叉搜寻树、AVL 树、红黑树、区间树、B 树等等，以应答不同的问题。
理解 Redis 数据库的敌人可能也晓得，Redis 提供列表、字符串、汇合等等几种罕用数据结构，然而对于每种数据结构，底层的存储形式都至多有两种，以便于依据存储数据的理论状况应用适合的存储形式。
综上，数据结构品种很多，甚至你也能够创造本人的数据结构，然而底层存储无非数组或者链表，二者的优缺点如下：
数组 因为是紧凑间断存储, 能够随机拜访，通过索引疾速找到对应元素，而且绝对节约存储空间。但正因为间断存储，内存空间必须一次性调配够，所以说数组如果要扩容，须要重新分配一块更大的空间，再把数据全副复制过来，工夫复杂度 O(N)；而且你如果想在数组两头进行插入和删除，每次必须搬移前面的所有数据以放弃间断，工夫复杂度 O(N)。
链表 因为元素不间断，而是靠指针指向下一个元素的地位，所以不存在数组的扩容问题；如果晓得某一元素的前驱和后驱，操作指针即可删除该元素或者插入新元素，工夫复杂度 O(1)。然而正因为存储空间不间断，你无奈依据一个索引算出对应元素的地址，所以不能随机拜访；而且因为每个元素必须存储指向前后元素地位的指针，会耗费绝对更多的贮存空间。
二、数据结构的基本操作
对于任何数据结构，其基本操作无非遍历 + 拜访，再具体一点就是：增删查改。
数据结构品种很多，但它们存在的目标都是在不同的利用场景，尽可能高效地增删查改。话说这不就是数据结构的使命么？
如何遍历 + 拜访？咱们依然从最高层来看，各种数据结构的遍历 + 拜访无非两种模式：线性的和非线性的。
线性就是 for/while 迭代为代表，非线性就是递归为代表。再具体一步，无非以下几种框架：
数组遍历框架，典型的线性迭代构造：
void traverse(int[] arr) {for (int i = 0; i < arr.length; i++) {// 迭代拜访 arr[i]
}
}链表遍历框架，兼具迭代和递归结构：
/* 根本的单链表节点 */
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)
}二叉树遍历框架，典型的非线性递归遍历构造：
/* 根本的二叉树节点 */
class TreeNode {
int val;
TreeNode left, right;
}
void traverse(TreeNode root) {traverse(root.left)
traverse(root.right)
}你看二叉树的递归遍历形式和链表的递归遍历形式，类似不？再看看二叉树构造和单链表构造，类似不？如果再多几条叉，N 叉树你会不会遍历？
二叉树框架能够扩大为 N 叉树的遍历框架：
/* 根本的 N 叉树节点 */
class TreeNode {
int val;
TreeNode[] children;}
void traverse(TreeNode root) {for (TreeNode child : root.children)
traverse(child);
}N 叉树的遍历又能够扩大为图的遍历，因为图就是好几 N 叉棵树的结合体。你说图是可能呈现环的？这个很好办，用个布尔数组 visited 做标记就行了，这里就不写代码了。
所谓框架，就是套路。不论增删查改，这些代码都是永远无奈脱离的构造，你能够把这个构造作为纲要，依据具体问题在框架上增加代码就行了，上面会具体举例。
三、算法刷题指南
首先要明确的是，数据结构是工具，算法是通过适合的工具解决特定问题的办法。也就是说，学习算法之前，最起码得理解那些罕用的数据结构，理解它们的个性和缺点。
那么该如何在 LeetCode 刷题呢？之前的文章算法学习之路写过一些，什么按标签刷，坚持下去云云。当初距那篇文章曾经过来将近一年了，我不说那些不痛不痒的话，间接说具体的倡议：
先刷二叉树，先刷二叉树，先刷二叉树！
这是我这刷题一年的亲自领会，下图是去年十月份的提交截图：
公众号文章的浏览数据显示，大部分人对数据结构相干的算法文章不感兴趣，而是更关怀动规回溯分治等等技巧。为什么要先刷二叉树呢，因为二叉树是最容易造就框架思维的，而且大部分算法技巧，实质上都是树的遍历问题。
刷二叉树看到题目没思路？依据很多读者的问题，其实大家不是没思路，只是没有了解咱们说的「框架」是什么。不要小看这几行破代码，简直所有二叉树的题目都是一套这个框架就进去了。
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 题，难度 Medium，让你依据前序遍历和中序遍历的后果还原一棵二叉树，很经典的问题吧，次要代码如下：
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 道，兴许你就有点本人的了解了；刷残缺个专题，再去做什么回溯动规分治专题，你就会发现只有波及递归的问题，都是树的问题。
再举例吧，说几道咱们之前文章写过的问题。
动静布局详解说过凑零钱问题，暴力解法就是遍历一棵 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)其实很多动静布局问题就是在遍历一棵树，你如果对树的遍历操作烂熟于心，起码晓得怎么把思路转化成代码，也晓得如何提取他人解法的外围思路。
再看看回溯算法，前文回溯算法详解罗唆间接说了，回溯算法就是个 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);
}N 叉树的遍历框架，找进去了把～你说，树这种构造重不重要？
综上，对于畏惧算法的敌人来说，能够先刷树的相干题目，试着从框架上看问题，而不要纠结于细节问题。
纠结细节问题，就比方纠结 i 到底应该加到 n 还是加到 n – 1，这个数组的大小到底应该开 n 还是 n + 1？
从框架上看问题，就是像咱们这样基于框架进行抽取和扩大，既能够在看他人解法时疾速了解外围逻辑，也有助于找到咱们本人写解法时的思路方向。
当然，如果细节出错，你得不到正确的答案，然而只有有框架，你再错也错不到哪去，因为你的方向是对的。
然而，你要是心中没有框架，那么你根本无法解题，给了你答案，你也不会发现这就是个树的遍历问题。
这种思维是很重要的，动静布局详解中总结的找状态转移方程的几步流程，有时候依照流程写出解法，说实话我本人都不晓得为啥是对的，反正它就是对了。。。
这就是框架的力量，可能保障你在快睡着的时候，仍然能写出正确的程序；就算你啥都不会，都能比他人高一个级别。
四、总结几句
数据结构的根本存储形式就是链式和程序两种，基本操作就是增删查改，遍历形式无非迭代和递归。
刷算法题倡议从「树」分类开始刷，联合框架思维，把这几十道题刷完，对于树结构的了解应该就到位了。这时候去看回溯、动规、分治等算法专题，对思路的了解可能会更加粗浅一些。