一、 什么是平衡二叉树？ 1.1 基本概念 平衡二叉树是一种特殊的二叉搜索树，它通过特定的平衡机制确保树的高度始终保持在对数级别。（解决了二叉搜索树的极端情况） 1.2 平衡条件 对于树中的任意节点，其左子树和右子树的高度差绝对值不超过1： 平衡因子 = 左子树高度 - 右子树高度 （注： 左 - 右） 平衡条件：|平衡因子| ≤ 1 二、为什么需要平衡二叉树？ 2.1 二叉搜索树的退化问题 有序

一、什么是二叉搜索树？ 二叉搜索树，也称为二叉排序树或二叉查找树，是一种特殊的二叉树。它或者是一棵空树，或者是具有下列性质的二叉树： 左子树上所有节点的值均小于它的根节点的值。 右子树上所有节点的值均大于它的根节点的值。 左、右子树也分别为二叉搜索树。 这个定义是递归的，它确保了整个树具有一个关键的属性：中序遍历二叉搜索树，可以得到一个升序排列的有序序列。 二、 核心性质与优点 有序性：结构本身隐

欧拉函数求质数 #include<iostream> using namespace std; typedef long long ll; const int N = 1e6 + 10; int euler, primes, cnt; bool st; void get_eulers(int n){ euler = 1; for(int i = 2; i <

一、最小生成树什么？ 1.1 定义 最小生成树： 一个有n个结点的连通图的生成树是原图的最小连通图，且包含原图的所有n个结点，并且保持图的连通的最少的边。 最小生成树可以用：Prim算法和kruskal算法求出 1.2 应用 铺设电缆： 以尽可能低的总价去铺设城市之间的电缆（假设每两个城市可以连通） 旅行家： 某人自驾游想花费最短的路程去旅行到自己所想去的城市（城市有n个 n > 2） 连接

一、最短路是什么？ 最短路径： 从某个点A（位置）到另一个点B(位置)的最短距离，实现方法：点A途中可以经过很多个点C，然后通过不断更新点A到途中点 C 的最短距离，最后实现最短距离到达 点B。 A -> C1 -> C2 -> C3 -> B 最短路径的分类： 单源最短路：图中的一个点到其余各点的最短路径 多源最短路：图中每两个点的最短路径 框架图解：（如果看不清的话，放

一、邻接表与邻接矩阵 1.1 稠密图与稀疏图 图的储存方式分两种：邻接表和邻接矩阵。 了解邻接矩阵和邻接表之前我们要先学会稠密图、稀疏图。 百度百科来说：稠密图、稀疏图。 稀疏图：有很少条边或弧（边的条数|E|远小于|V|²）的图称为稀疏图（sparse graph）。 稠密图：有很多条边或弧 (边的条数|E|接近|V|²) 的图称为稠密图（dense graph）。 简单来说：我们假设某个图的点

一、BFS是什么 先用百度百科的来讲： BFS（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和广度优先搜索类似的思想。属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。 简单来说，BFS是一种图搜索的算法

一、DFS是什么？ DFS（深度优先搜索算法）：一种用于遍历或者树或者图的算法，是一种递归程序，不断递归达到无法在到达的点，简单点来说：一条路一直走，走到没有路后就原路返回，重新选择另一条 dfs(step + 1)。 DFS = 暴搜 + 回溯算法 + 剪枝（大多数是这样）。DFS需要回溯算法，其他算法也需要回溯算法，两种是一种调用关系。 暴搜：一条路走到黑（直接递归走到底） 回溯：DFS 开启

一、KMP是什么 KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，用于在文本中查找模式。它的核心思想是利用已经匹配的信息来避免重复匹配，从而提高效率。 二、暴力字符串匹配 暴时间复杂度O（n * m） //大概是这样的，可能有差别，但是模板基本上是这样 for (int i = 0; i < m;) { int j = 0; while (i < m &a

一、Trie树是什么？ Trie树又称字典树或前缀树，是一种能够快速查找一组字符串含有一个字符串的类似哈希表的树结构，是以空间换时间，利用字符串的前缀来降低查询时间。 与二叉树不同，Trie树有26子节点对应26个字母，根节点不包含字符串，从根节点到某个节点，经过的字符连起来的字符串就是对应的字符串。当储存结束一个字符串后，尾节点会用cnt数组来说明该字符串的次数。 二、怎么建立Trie树