LeetCode 题解之路：基础数据结构总览——从数组、队列到树与图的前端实战解读

LeetCode 题解之路基础数据结构总览——从数组、队列到树与图的前端实战解读【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇技术指南以 leetcode 开源题解仓库中的《基础的数据结构总览》为核心骨架结合仓库内的 二叉树的遍历、图专题 以及 problems 目录下的具体题目用现实场景React Hooks、HTTP 队头阻塞、浏览器执行栈、React Fiber、ImmutableJS 等串讲线性与非线性两大类数据结构。读完本文你将掌握数组、队列、栈、链表、树、堆、二叉查找树、字典树与图的核心特征与适用场景并能在 LeetCode 刷题时快速把题目对应到正确的数据结构选型上。开篇定位这是一篇复习 场景理解指南需要先说明的是这份文档并不是一篇从零讲解数据结构定义的教学文章而是一份面向有一定基础读者的复习与深化指南它不纠结于教科书式的概念罗列而是把每个数据结构和前端 / 工程中的真实场景绑定帮助读者理解并复习数据结构与算法。文档的定位明确偏向前端——通过学习前端实际场景中出现的数据结构加深对数据结构本身的认识。如果你的数据结构基础比较薄弱建议先阅读基础教程再回到本文。从逻辑上数据结构可以分为线性结构数组、栈、链表等与非线性结构树、图等。这里需要特别注意线性和非线性不代表存储结构是线性的还是非线性的两者没有任何关系它只是一种逻辑上的划分——例如完全可以用数组去存储二叉树。一般而言有前驱和后继的就是线性数据结构数组和链表就是典型代表。线性结构数组一切数据结构的影子数组是最简单的数据结构很多地方都在使用它例如用一个数据列表存储一批用户 ID。更重要的是后面要讲的栈和队列本质上都可以看成是受限的数组——区别只在于限制了什么操作。理解了这一点后续内容会顺畅很多。实战场景React Hooks 的本质就是一个数组非前端党慎入React Hooks 的底层本质就是数组。看下面的伪代码function Form() { // 1. Use the name state variable const [name, setName] useState(Mary); // 2. Use an effect for persisting the form useEffect(function persistForm() { localStorage.setItem(formData, name); }); // 3. Use the surname state variable const [surname, setSurname] useState(Poppins); // 4. Use an effect for updating the title useEffect(function updateTitle() { document.title name surname; }); // . . . }基于数组的实现方式Form 的 hooks 就是[hook1, hook2, hook3, hook4]其中 hook1 就是[name, setName]这一对hook2 就是persistForm这个 effect。之所以用数组而非对象可以从反面来理解如果换成对象实现Form 的 hooks 会变成{ key1: hook1, key2: hook2, key3: hook3, key4: hook4, }那么问题就来了key1、key2、key3、key4 该怎么取这本身就是个难题。数组方案用位置天然解决了索引问题。不过使用数组也有代价React 把如何确保组件内部 hooks 保存的状态之间的对应关系这个工作交给了开发人员——你必须保证 hooks 的调用顺序严格一致即 React 官网 Hooks 规则中所要求的。这也是为什么 hooks 不能写在条件分支里。关于 React hooks 本质的更多研究可参考社区文章 React hooks: not magic, just arrays。队列只在两端操作的受限序列队列是一种受限的序列。受限在哪它只能够操作队尾和队首只能在队尾添加元素入队在队首删除元素出队而数组没有这个限制。这个名字可以类比现实生活中的排队——那种不插队的排队。在计算机科学中队列是一种特殊类型的抽象数据类型或集合集合中的实体按顺序保存。队列的两种基本操作是向队列的后端位置添加实体称为入队enqueue从队列的前端位置移除实体称为出队dequeue。队列中元素遵循先进先出FIFO, first in, first out的原则。队列是最常见的数据结构之一应用极其广泛例如消息队列。实战场景HTTP 1.1 的队头阻塞问题做性能优化时我们常听到HTTP 1.1 的队头阻塞问题HTTP/2 解决了 HTTP/1.1 中的队头阻塞但很多人并不清楚 HTTP/1.1 为什么会有队头阻塞、HTTP/2 又是怎么解决的。实际上队头阻塞head-of-line blocking是一个专有名词不仅出现在 HTTP 中交换机等领域也有。它的根本原因就是使用了队列这种数据结构。HTTP/1.0 的客户端队头阻塞协议规定对于同一个 TCP 连接所有 HTTP/1.0 请求放入队列只有前一个请求的响应收到之后才能发送下一个请求此时就会发生阻塞且这种阻塞主要发生在客户端。就像在等红绿灯即使旁边的车道绿灯亮了你这个车道是红灯还是不能走。HTTP/1.1 的管道PipelineHTTP/1.1 中每一个连接默认是长连接persistent connection允许一次发送多个请求不必等前一个响应收到就能发送下一个从而解决了 HTTP/1.0 客户端的队头阻塞——这就是 HTTP/1.1 中管道的概念。HTTP/1.1 的服务器端队头阻塞但 HTTP/1.1 规定服务器端响应的发送必须根据请求被接收的顺序排队——先接收到的请求其响应也必须先发送。如果最先收到的请求处理时间很长、响应生成慢就会阻塞已经生成好的响应的发送造成新的队头阻塞。可见 HTTP/1.1 的队头阻塞发生在服务器端。HTTP/2 的解法为了解决服务器端队首阻塞HTTP/2 采用了二进制分帧与多路复用。帧是 HTTP/2 数据通信的最小单位——HTTP/1.1 的数据包是文本格式HTTP/2 的数据包是二进制格式二进制帧。帧的传输方式可以将请求和响应数据分割得更小且二进制协议能被高效解析同一域名下的所有通信在单个连接上完成可以承载任意数量的双向数据流每个数据流以消息形式发送消息又由一个或多个帧组成帧之间可以乱序发送再根据帧首部的流标识重新组装。多路复用取代了原来的序列与拥塞机制HTTP/1.1 并发多个请求需要多个 TCP 连接且单个域名有 6-8 个 TCP 连接的限制浏览器限制各浏览器可能不同HTTP/2 中同一域名下的所有通信在单个连接完成仅占用一个 TCP 连接可并行请求和响应、互不干扰。队列在 LeetCode 题解仓库中也有直接体现例如 232. 用栈实现队列其前置知识就标注为栈 队列。栈只在栈顶操作的受限序列栈也是一种受限的序列受限之处在于只能够操作栈顶不管入栈还是出栈都是在栈顶操作。栈是一种抽象数据类型表示元素的集合具有两种主要操作push添加元素到栈的顶端末尾pop移除栈最顶端末尾的元素。以上两种操作可以概括为后进先出LIFO, last in, first out。此外通常还有一个peek操作用于访问当前栈顶元素只返回不弹出。栈这个名字可以类比一组物体的堆叠——一摞书、一摞盘子。实战场景浏览器执行栈与递归栈在很多地方都有应用浏览器中就充满了栈。浏览器的执行栈call stack就是一个基本的栈结构。这也就解释了为什么递归的解法和循环 栈的解法本质上差不多——因为递归在底层正是借助调用栈执行的。例如下面这段 JS 代码function bar() { const a 1; const b 2; console.log(a, b); } function foo() { const a 1; bar(); } foo();真正执行的时候内部就是一层层压栈、出栈的过程图中所绘只展示栈帧未画出执行上下文中 this 和 scope 等其他部分这部分是闭包的关键此处讲解栈不展开。这里顺带澄清一个常见误区社区中执行上下文中的 scope 指的是执行栈中父级声明的变量的说法是完全错误的——JS 是词法作用域scope 指的是函数定义时的父级与执行无关。栈的常见应用还有进制转换、括号匹配、栈混洗stack shuffling、中缀表达式用的很少、后缀表达式逆波兰表达式等。其中合法的栈混洗操作与合法的括号匹配表达式之间存在一一对应关系n 个元素的栈混洗有多少种n 对括号的合法表达式就有多少种。链表基础中的基础链表是最基本的数据结构之一熟练掌握链表的结构和常见操作是基础中的基础。与数组的连续存储不同链表通过指针把节点串起来插入删除无需移动大量元素代价是无法随机访问。栈、队列都可以用链表实现。实战场景React Fiber 为什么基于链表非前端慎入很多人都知道 fiber 是基于链表实现的但为什么要基于链表把fiber 和链表这两个点放在一起讲就清楚了。Fiber 出现的目的是解决 React 在执行时无法停下来、需要一口气执行完的问题。在引入 Fiber 之前React 的协调过程会阻塞主线程导致高优先级的代码如用户输入无法及时执行。因此 React 团队打算自建一个**虚拟执行栈**来解决这个问题而这个虚拟执行栈的底层实现就是链表。Fiber 的基本原理是把协调过程分成小块一次执行一块然后将运算结果保存起来并判断是否有时间继续执行下一块React 自己实现了一个类似requestIdleCallback的功能。如果有时间就继续否则跳出让浏览器主线程歇一会、去执行高优先级代码。当协调过程完成所有小块都运算完毕才进入提交阶段执行真正的副作用操作如更新 DOM这个过程无法取消——因为这部分有副作用。这种划分成块、最后合并的思路有点像 Map/Reduce。换句话说React 必须重新实现遍历树的算法从依赖于内置堆栈的同步递归模型变为具有链表和指针的异步模型。正如 React 团队成员 Andrew 所说如果只依赖内置调用堆栈它将继续工作直到堆栈为空。而如果能随意中断调用堆栈、手动操作栈帧问题就解决了——这正是 React Fiber 的目的Fiber 是堆栈的重新实现专门用于 React 组件可以把单个 Fiber 看作一个虚拟堆栈帧。React Fiber 大概是这样的let fiber { tag: HOST_COMPONENT, type: div, return: parentFiber, children: childFiber, sibling: childFiber, alternate: currentFiber, stateNode: document.createElement(div), props: { children: [], className: foo }, partialState: null, effectTag: PLACEMENT, effects: [], };从这段代码可以看出fiber 本质上是一个对象使用return、children、sibling属性构建 fiber 树来表示组件的结构树而这些字段的值本身也是 fiber因此 fiber 看起来就是一个链表。细心的读者可能已经注意到alternate也是一个 fiber——它的原理有点像 git可以用来执行 git revert、git commit 等类似操作用于双缓冲与回滚。非线性结构有了线性结构为什么还需要非线性结构答案是为了高效地兼顾静态操作和动态操作我们一般使用树去管理需要大量动态操作的数据。可以对照各种数据结构各种操作的复杂度来直观感受这一点。树无处不在的递归结构树的应用非常广泛小到文件系统大到因特网、组织架构都可以表示为树结构。对前端而言熟悉的 DOM 树就是一种树结构HTML 本质上是一种 DSL领域特定语言用来描述这种树结构的具体表现形式AST抽象语法树也是一种树XML 同样是树结构。树的应用远比大多数人想象的要多得多。从图论角度树是一种特殊的图它是无环连通图是极大无环图也是极小连通图。从另一个角度看树是一种递归的数据结构而且树的不同表示方法——比如不常用的长子 兄弟法——对理解树的本质有很大帮助。树的基本算法包括前中后序遍历和层次遍历。对于前中后这三个顺序容易混淆的读者只需要记住一句话所谓的前中后指的是根节点的位置其他位置按照先左后右排列即可——前序遍历是根左右中序是左根右后序是左右根。由于树是递归的数据结构用递归完成树的遍历非常简单而树的算法基本都依赖于遍历。但递归在计算机中的性能一直是个问题因此掌握不那么容易理解的命令式迭代遍历算法在某些情况下很有用——如果使用迭代方式遍历可以借助前面提到的栈来进行能极大减少代码量。注意由于栈是 FILO后进先出的使用栈简化运算时一定要注意左右子树的推入顺序。树的两个重要性质如果树有 n 个顶点那么它有 n-1 条边——说明树的顶点数和边数是同阶的任何一个节点到根节点存在唯一路径路径的长度即节点所处的深度。实际使用的树可能更复杂例如游戏中的碰撞检测可能用到四叉树或八叉树以及 k 维的树结构 k-d 树等。仓库 thinkings 目录下的 树专题 对树的各类问题有更深入的展开。二叉树被限制却足以描述一切树二叉树是节点度数不超过 2 的树是树的一种特殊子集。有趣的是二叉树这种被限制的树结构却能够表示和实现所有的树——它背后的原理正是长子 兄弟法。正如邓俊辉老师所说二叉树是多叉树的特例但在有根且有序时其描述能力却足以覆盖后者。实际上在使用长子 兄弟法表示树的同时旋转 45 度角即可直观看出这种等价关系。对于一般的树我们通常会去遍历这里又会有很多变种。仓库中与二叉树遍历直接相关的题目包括94. 二叉树的中序遍历102. 二叉树的层序遍历103. 二叉树的锯齿形层序遍历144. 二叉树的前序遍历145. 二叉树的后序遍历199. 二叉树的右视图相关概念真二叉树——所有节点的度数只能是偶数即只能为 0 或 2。仓库还专门开设了 二叉树的遍历 章节从DFS 可用栈简化操作BFS 如何记录每层是否遍历完成等关键点切入对前中后序与层次遍历的具体细节和算法进行了系统讲解。其中值得注意的要点是前序遍历入栈时应先将右节点入栈、再入左节点中序遍历一棵二叉查找树BST的结果是有序数组利用这个性质可以简化 230. 二叉搜索树中第 K 小的元素 这类题目。堆优先队列的典型实现堆heap其实是一种优先级队列。很多语言都有对应的内置数据结构遗憾的是 JavaScript 没有这种原生数据结构但这不影响我们的理解与应用。堆的一种典型实现就是二叉堆。二叉堆的特点在**最小堆min heap**中如果 P 是 C 的一个父级节点那么 P 的 key或 value应小于或等于 C 的对应值。正因为此堆顶元素一定是最小的我们常利用这个特点求最小值或第 k 小的值。在**最大堆max heap**中P 的 key或 value大于或等于 C 的对应值因此堆顶元素一定是最大的。需要注意的是优先队列不仅有堆这一种实现还有更复杂的实现但通常来说我们会把两者做等价。仓库中直接相关的经典题目是 295. 数据流的中位数。这道题求动态数据的中位数LeetCode 难度为 hard如果求静态数据的中位数用数组存储即可 O(1) 查询但动态插入每次排序会达到 O(n log n) O(1)容易超时。借助堆可以这样优化建立两个堆一个大顶堆、一个小顶堆满足两个条件——① 大顶堆元素都比小顶堆元素小由于堆的特点其实只要比较堆顶即可② 大顶堆元素个数不小于小顶堆且最多比小顶堆多一个。这样找中位数时如果两个堆数量相等总数为偶数取两个堆顶元素的平均数如果不相等总数为奇数取大顶堆的堆顶元素。该题中作者也提醒JavaScript 没有原生的优先级队列可使用社区实现不必纠结于优先级队列的实现细节。二叉查找树为什么它适合查找二叉排序树Binary Sort Tree又称二叉查找树Binary Search Tree亦称二叉搜索树。它是一棵具有下列性质的二叉树若左子树不空则左子树上所有节点的值均小于它的根节点的值若右子树不空则右子树上所有节点的值均大于它的根节点的值左、右子树也分别为二叉排序树没有键值相等的节点。对于一个二叉查找树常规操作有插入、查找、删除、找父节点、求最大值、求最小值。它之所以叫查找树就是因为其非常适合查找——例如在一棵二叉查找树中找值小于且最接近 58的节点搜索流程沿着树逐层比较即可快速收敛。另外二叉查找树还有一个重要性质其中序遍历的结果是一个有序数组。有时候可以利用这个性质来简化问题。仓库中对应的验证题目是 98. 验证二叉搜索树——其解法正是利用中序遍历结果为有序数组的性质中序遍历后两两判断是否存在逆序元素对即可该题也提供了定义法每个节点必须落在某个取值范围 (min, max) 内递归向下收窄区间。二叉平衡树把查询降到 O(log n)平衡树是一类数据结构是改进的二叉查找树。一般的二叉查找树查询复杂度取决于目标节点到树根的距离深度因此当节点深度普遍较大时查询的均摊复杂度会上升为了实现更高效的查询产生了平衡树。这里的平衡指所有叶子的深度趋于平衡更广义地指树上所有可能查找的均摊复杂度偏低。一些数据库引擎内部就使用这种数据结构目标是把查询操作降到 O(log n)即树的深度——可以简单理解为树在数据结构层面构造了二分查找算法。平衡树的基本操作包括旋转、插入、删除、查询前驱、查询后继。AVL 树最早被发明的自平衡二叉查找树。在 AVL 树中任一节点对应的两棵子树的最大高度差为 1因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是 O(log n)增加和删除元素可能借由一次或多次树旋转来实现重新平衡。AVL 树得名于发明者 G. M. Adelson-Velsky 和 Evgenii Landis他们在 1962 年的论文An algorithm for the organization of information中公开了这一数据结构。节点的平衡因子是它的左子树高度减去右子树高度有时相反平衡因子为 1、0 或 -1 的节点被认为是平衡的而 -2 或 2 的节点被认为是不平衡的、需要重新平衡。红黑树1972 年由鲁道夫·贝尔发明最初被称为对称二叉 B 树现代名字源于 Leo J. Guibas 和 Robert Sedgewick 于 1978 年的论文。红黑树结构复杂但操作有良好的最坏情况运行时间并且在实践中高效它可以在 O(log n) 时间内完成查找、插入和删除n 是树中元素的数目。Java 的 TreeMap/TreeSet、C STL 的 map/set 等都是以红黑树为典型代表的内置实现。字典树前缀树利用公共前缀的字符串结构字典树又称 Trie 树是一种树形结构典型应用是统计、排序和保存大量的字符串但不仅限于字符串因此经常被搜索引擎系统用于文本词频统计。它的优点是利用字符串的公共前缀来减少查询时间最大限度地减少无谓的字符串比较查询效率比哈希树高。它有 3 个基本性质根节点不包含字符除根节点外每一个节点都只包含一个字符从根节点到某一节点路径上经过的字符连接起来为该节点对应的字符串每个节点的所有子节点包含的字符都不相同。实战场景ImmutableJS 与字典树非前端慎入immutableJS的底层就是share tree结构共享 树这样看的话其实和字典树是一致的通过共享未改变的子树来降低拷贝成本。仓库 208. 实现 Trie前缀树 直接考察了字典树的实现——该题的解法要点是为了区分search和startsWith需要在节点中增加一个标示来区分当前节点是否是某个单词的结尾节点结构大致是TrieNode含当前字母、子节点映射、是否单词结尾标志。仓库中与字典树相关的题目还有211. 添加与搜索单词 - 数据结构设计212. 单词搜索 II图最复杂的数据结构图论Graph Theory是数学的一个分支以图为研究对象。图论中的图由若干给定的点及连接两点的线构成用点代表事物用连接两点的线表示两个事物间的关系。图是一种最复杂的数据结构前面讲的数据结构都可以看成是图的特例。那为什么不都用图就好了还要分那么多种数据结构呢这是因为很多时候不需要用到那么复杂的功能——给各种特殊的图起特殊的名字是为了方便沟通直到遇到非常复杂的情况我们才会用到真正的图。什么时候需要用图来存储数据答案很简单如果用其他简单的数据结构无法很好地存储就应该使用图了。比如需要存储一种双向的、多对多的朋友关系就一定要用到图因为其他数据结构无法模拟。关于图的完整知识体系无向图与有向图、有权图与无权图、入度与出度、路径与环、连通图与强连通图、生成树与最小生成树、建图方法、遍历与经典算法等仓库中专门开设了 图专题可前往该章节系统学习。仓库中图相关的题目示例包括 200. 岛屿数量、547. 省份数量 等分别体现了 DFS/BFS 与并查集在图连通性问题上的应用。小结数据结构选型的心智模型纵观这份总览可以提炼出几条刷题与工程实践通用的心智模型受限即优势栈和队列都是受限的数组/序列限制操作面恰恰带来了语义清晰的 FIFO / LIFO 特性也让代码更易推理递归结构与栈天然绑定树是递归结构递归遍历与栈 迭代遍历本质等价浏览器执行栈、React Fiber 都是这一思想的工程化体现二叉树是万能表达层二叉树的描述能力足以覆盖所有树遍历前中后序 层次是几乎所有树类题目的基础操作详见 二叉树的遍历按操作复杂度选型动态增删频繁的数据交给树含堆、平衡树静态有序查询交给数组或二叉查找树字符串批量处理优先想到字典树关系复杂到无法用线性结构表达时则上升到图见 图专题。以此为骨架再配合仓库 problems 目录下大量按数据结构和算法归类的题目进行刻意练习就能把认识数据结构转化为为题目选对数据结构的实战能力。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考