// 中序遍历迭代版：使用显式栈 voidinorder_iter(TreeNode* root){ std::stack<TreeNode*> stk; TreeNode* cur = root; while (cur || !stk.empty()) { // 一路向左压栈 while (cur) { stk.push(cur); cur = cur->left; } // 弹出访问，转向右子树 cur = stk.top(); stk.pop(); visit(cur); cur = cur->right; } }
图解步骤：
graph TB
A["开始\ncur=root"]
B["向左一路压栈\ncur=cur->left"]
C{"cur==null?"}
D["弹栈访问\ncur=stk.top()"]
E["cur=cur->right"]
F["结束"]
A --> B
B --> C
C -->|"否"| B
C -->|"是"| D
D --> E
E --> B
E -.->|"stk空&cur空"| F
style A fill:#C7CEEA,stroke:#9FA8DA,color:#333
style B fill:#E8D5F5,stroke:#CE93D8,color:#333
style C fill:#FFF9C4,stroke:#F9A825,color:#333
style D fill:#B5EAD7,stroke:#80CBC4,color:#333
style E fill:#FFDAB9,stroke:#FFAB76,color:#333
style F fill:#FFB3C6,stroke:#F48FB1,color:#333
3.3 前序遍历：迭代版
1 2 3 4 5 6 7 8 9 10 11 12 13
// 前序遍历迭代版：根 -> 左 -> 右 voidpreorder_iter(TreeNode* root){ if (!root) return; std::stack<TreeNode*> stk; stk.push(root); while (!stk.empty()) { TreeNode* node = stk.top(); stk.pop(); visit(node); // 栈是 LIFO，先压右再压左，弹出时才是 左 -> 右 if (node->right) stk.push(node->right); if (node->left) stk.push(node->left); } }
3.4 后序遍历：迭代版（最难）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
// 后序遍历迭代版：左 -> 右 -> 根 // 思路：前序是 根->左->右，反过来是 根->右->左，再 reverse 就是 后序 voidpostorder_iter(TreeNode* root){ if (!root) return; std::stack<TreeNode*> stk; std::vector<int> out; stk.push(root); while (!stk.empty()) { TreeNode* node = stk.top(); stk.pop(); out.push_back(node->val); if (node->left) stk.push(node->left); if (node->right) stk.push(node->right); } std::reverse(out.begin(), out.end()); // 反转得到后序 for (int v : out) visit_dummy(v); }
3.5 层序遍历：BFS 模板
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
// 层序遍历（BFS）：用队列实现，按层访问 std::vector<std::vector<int>> levelOrder(TreeNode* root) { std::vector<std::vector<int>> ans; if (!root) return ans; std::queue<TreeNode*> q; q.push(root); while (!q.empty()) { int sz = q.size(); // 关键：保存当前层大小 std::vector<int> level; for (int i = 0; i < sz; ++i) { TreeNode* node = q.front(); q.pop(); level.push_back(node->val); if (node->left) q.push(node->left); if (node->right) q.push(node->right); } ans.push_back(level); } return ans; }
TreeNode* helper(std::vector<int>& pre, int pl, int pr, std::vector<int>& in, int il, int ir, std::unordered_map<int, int>& mp){ if (pl > pr || il > ir) returnnullptr; int root_val = pre[pl]; int idx = mp[root_val]; // O(1) 定位 int left_size = idx - il; TreeNode* root = newTreeNode(root_val); root->left = helper(pre, pl + 1, pl + left_size, in, il, idx - 1, mp); root->right = helper(pre, pl + left_size + 1, pr, in, idx + 1, ir, mp); return root; }
graph TD
A["插入新节点（红色）"]
B{"父节点是黑色？"}
C["✅ 结束，无须修复"]
D{"叔节点是红色？"}
E["Case 1\n父叔变黑\n祖父变红\n向上递归"]
F{"当前节点是内侧？"}
G["Case 2\n旋转父节点\n转为 Case 3"]
H["Case 3\n父变黑\n祖父变红\n旋转祖父"]
A --> B
B -->|"是"| C
B -->|"否"| D
D -->|"是"| E
D -->|"否"| F
F -->|"是"| G
F -->|"否"| H
style A fill:#C7CEEA,stroke:#9FA8DA,color:#333
style B fill:#FFF9C4,stroke:#F9A825,color:#333
style C fill:#B5EAD7,stroke:#80CBC4,color:#333
style D fill:#FFF9C4,stroke:#F9A825,color:#333
style E fill:#FFDAB9,stroke:#FFAB76,color:#333
style F fill:#FFF9C4,stroke:#F9A825,color:#333
style G fill:#E8D5F5,stroke:#CE93D8,color:#333
style H fill:#FFB3C6,stroke:#F48FB1,color:#333
graph TB
A["插入键到满节点\n（4 键，5 子）"]
B["取中间键\n（中位数）"]
C["中间键上提到父"]
D["分裂成两个节点\n左 ⌈m/2⌉-1 键\n右 ⌈m/2⌉-1 键"]
E{"父节点也溢出？"}
F["递归分裂"]
G["✅ 结束"]
A --> B --> C --> D
D --> E
E -->|"是"| F --> D
E -->|"否"| G
style A fill:#FFB3C6,stroke:#F48FB1,color:#333
style B fill:#FFF9C4,stroke:#F9A825,color:#333
style C fill:#E8D5F5,stroke:#CE93D8,color:#333
style D fill:#FFDAB9,stroke:#FFAB76,color:#333
style E fill:#FFF9C4,stroke:#F9A825,color:#333
style F fill:#E8D5F5,stroke:#CE93D8,color:#333
style G fill:#B5EAD7,stroke:#80CBC4,color:#333
// 插入单词 voidinsert(const std::string& word){ TrieNode* node = root; for (char c : word) { int idx = c - 'a'; if (!node->children[idx]) { node->children[idx] = newTrieNode(); } node = node->children[idx]; } node->isEnd = true; // 标记单词结尾 }
// 查找完整单词 boolsearch(const std::string& word){ TrieNode* node = root; for (char c : word) { int idx = c - 'a'; if (!node->children[idx]) returnfalse; node = node->children[idx]; } return node->isEnd; // 必须以 isEnd 结尾 }
// 查找前缀 boolstartsWith(const std::string& prefix){ TrieNode* node = root; for (char c : prefix) { int idx = c - 'a'; if (!node->children[idx]) returnfalse; node = node->children[idx]; } returntrue; // 路径存在即可 } };
8.4 Trie 图示
graph TB
ROOT["(root)\nisEnd=F"]
A["a\nisEnd=F"]
P["p\nisEnd=F"]
P2["p\nisEnd=F"]
L["l\nisEnd=F"]
E["e\nisEnd=T\n(apple)"]
I["i\nisEnd=F"]
D["d\nisEnd=T\n(appid)"]
ROOT --> A
A --> P
P --> P2
P2 --> L
L --> E
P2 --> I
I --> D
style ROOT fill:#C7CEEA,stroke:#9FA8DA,color:#333
style A fill:#E8D5F5,stroke:#CE93D8,color:#333
style P fill:#E8D5F5,stroke:#CE93D8,color:#333
style P2 fill:#FFDAB9,stroke:#FFAB76,color:#333
style L fill:#FFDAB9,stroke:#FFAB76,color:#333
style E fill:#B5EAD7,stroke:#80CBC4,color:#333
style I fill:#FFDAB9,stroke:#FFAB76,color:#333
style D fill:#B5EAD7,stroke:#80CBC4,color:#333
graph TB
A["a(45)\nb(13)\nc(12)\nd(16)\ne(9)\nf(5)"]
B["(1) 取出 f(5) + e(9)\n合并为 (14)"]
C["(2) 取出 (14) + c(12)\n合并为 (26)"]
D["(3) 取出 b(13) + d(16)\n合并为 (29)"]
E["(4) 取出 (26) + (29)\n合并为 (55)"]
F["(5) 取出 a(45) + (55)\n合并为 (100)"]
G["哈夫曼树根"]
A --> B --> C --> E --> F --> G
A --> D --> E
style A fill:#C7CEEA,stroke:#9FA8DA,color:#333
style B fill:#E8D5F5,stroke:#CE93D8,color:#333
style C fill:#FFDAB9,stroke:#FFAB76,color:#333
style D fill:#E8D5F5,stroke:#CE93D8,color:#333
style E fill:#FFDAB9,stroke:#FFAB76,color:#333
style F fill:#FFB3C6,stroke:#F48FB1,color:#333
style G fill:#B5EAD7,stroke:#80CBC4,color:#333
graph TB
ROOT["1\n(下标 0)"]
L["2\n(下标 1)"]
R["3\n(下标 2)"]
LL["4\n(下标 3)"]
LR["5\n(下标 4)"]
RL["6\n(下标 5)"]
RR["7\n(下标 6)"]
ROOT --> L
ROOT --> R
L --> LL
L --> LR
R --> RL
R --> RR
style ROOT fill:#FFB3C6,stroke:#F48FB1,color:#333
style L fill:#FFDAB9,stroke:#FFAB76,color:#333
style R fill:#FFDAB9,stroke:#FFAB76,color:#333
style LL fill:#B5EAD7,stroke:#80CBC4,color:#333
style LR fill:#B5EAD7,stroke:#80CBC4,color:#333
style RL fill:#B5EAD7,stroke:#80CBC4,color:#333
style RR fill:#B5EAD7,stroke:#80CBC4,color:#333
数组存储：[1, 2, 3, 4, 5, 6, 7]
10.3 堆化操作（Heapify）
向下调整（sift down）：
1 2 3 4 5 6 7 8 9 10 11 12
// 向下调整：把 i 位置的元素下沉到正确位置 // 用于删除堆顶后重建堆 voidsiftDown(std::vector<int>& heap, int i, int n){ while (true) { int l = 2 * i + 1, r = 2 * i + 2, largest = i; if (l < n && heap[l] > heap[largest]) largest = l; if (r < n && heap[r] > heap[largest]) largest = r; if (largest == i) break; std::swap(heap[i], heap[largest]); i = largest; } }
向上调整（sift up）：
1 2 3 4 5 6 7 8 9 10
// 向上调整：把 i 位置的元素上浮到正确位置 // 用于插入新元素 voidsiftUp(std::vector<int>& heap, int i){ while (i > 0) { int parent = (i - 1) / 2; if (heap[parent] >= heap[i]) break; // 大顶堆 std::swap(heap[i], heap[parent]); i = parent; } }
// DFS 递归模板 voiddfs(const std::vector<std::vector<int>>& adj, int u, std::vector<bool>& visited){ visited[u] = true; // visit(u) // 访问当前节点 for (int v : adj[u]) { if (!visited[v]) dfs(adj, v, visited); } }
// DFS 迭代模板（用栈模拟） voiddfsIter(const std::vector<std::vector<int>>& adj, int start){ int n = adj.size(); std::vector<bool> visited(n, false); std::stack<int> stk; stk.push(start); while (!stk.empty()) { int u = stk.top(); stk.pop(); if (visited[u]) continue; visited[u] = true; // visit(u) // 逆序压栈，保证出栈顺序与递归一致 for (auto it = adj[u].rbegin(); it != adj[u].rend(); ++it) { if (!visited[*it]) stk.push(*it); } } }
12.3 BFS vs DFS
维度
BFS
DFS
数据结构
队列
栈（递归）
空间
O(w)（w = 最宽层宽）
O(h)（h = 最深深度）
最短路径
✅ 无权图最短
❌
环检测
需要标记
天然支持
路径问题
适合
适合
实现难度
简单
简单
内存爆炸
队列大时 OOM
栈深时 OOM
12.4 BFS 时序图
sequenceDiagram
actor U as 👤 用户
participant BFS as 🟢 BFS
participant Q as 📦 队列
participant V as 🗄️ 图
U->>BFS: 调用 bfs(start)
BFS->>Q: push(start), dist[start]=0
loop 队列非空
BFS->>Q: pop()
BFS->>V: 查询 u 的邻居
V-->>BFS: [v1, v2, v3]
BFS->>Q: push(未访问的)
end
BFS-->>U: 返回 dist[] 数组
十三、最短路径：Dijkstra 与 Floyd
13.1 三种最短路算法对比
算法
适用
负权
时间
思想
Dijkstra
单源、正权
❌
O((V+E) log V)
贪心 + 优先队列
Bellman-Ford
单源、可负权
✅
O(VE)
松弛 V-1 次
SPFA
单源、可负权
✅
平均 O(E)
队列优化 Bellman
Floyd-Warshall
多源
✅
O(V³)
DP 转移
BFS
单源、无权
-
O(V+E)
层序遍历
13.2 Dijkstra 算法详解
核心思想：贪心 + 优先队列。每次从未访问的节点中选距离最小的，更新邻居距离。
graph TD
A["初始化：dist[src]=0，其他=∞"]
B["将 src 入小顶堆 {dist, node}"]
C["弹出堆顶 u（最小 dist）"]
D{"u 已访问？"}
E["遍历 u 的所有邻居 v"]
F["松弛：dist[v] > dist[u] + w(u,v) ?"]
G["更新 dist[v]，入堆"]
H["标记 u 已访问"]
I{"堆空？"}
J["✅ 结束，dist[] 即答案"]
A --> B --> C --> D
D -->|"是"| I
D -->|"否"| E
E --> F
F -->|"是"| G
F -->|"否"| E
G --> E
E -->|"结束"| H --> I
I -->|"否"| C
I -->|"是"| J
style A fill:#C7CEEA,stroke:#9FA8DA,color:#333
style B fill:#E8D5F5,stroke:#CE93D8,color:#333
style C fill:#FFDAB9,stroke:#FFAB76,color:#333
style D fill:#FFF9C4,stroke:#F9A825,color:#333
style E fill:#FFDAB9,stroke:#FFAB76,color:#333
style F fill:#FFF9C4,stroke:#F9A825,color:#333
style G fill:#B5EAD7,stroke:#80CBC4,color:#333
style H fill:#E8D5F5,stroke:#CE93D8,color:#333
style I fill:#FFF9C4,stroke:#F9A825,color:#333
style J fill:#B5EAD7,stroke:#80CBC4,color:#333
// Dijkstra 完整实现 // 返回从 src 到所有点的最短距离 std::vector<int> dijkstra(const std::vector<std::vector<std::pair<int,int>>>& adj, int src){ int n = adj.size(); std::vector<int> dist(n, INT_MAX); dist[src] = 0; // 小顶堆：{距离, 节点} using PII = std::pair<int,int>; std::priority_queue<PII, std::vector<PII>, std::greater<PII>> pq; pq.push({0, src}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; // 跳过过时的条目 for (auto [v, w] : adj[u]) { if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; // 松弛 pq.push({dist[v], v}); } } } return dist; }
13.4 Dijkstra 为什么不能处理负权？
反例：
graph LR
A["A\ndist=0"] -->|"6"| B["B\ndist=6"]
A -->|"3"| C["C\ndist=3"]
B -->|"−4"| C
style A fill:#C7CEEA,stroke:#9FA8DA,color:#333
style B fill:#FFDAB9,stroke:#FFAB76,color:#333
style C fill:#B5EAD7,stroke:#80CBC4,color:#333
Dijkstra 第一步：选 A，松弛 B=6, C=3
Dijkstra 第二步：选 C（dist=3 最小），标记 C 已访问
实际上 A→B→C = 6+(-4) = 2 < 3
但 C 已被标记，Dijkstra 错过更新
根本原因：Dijkstra 的”已访问即最优”假设在负权下不成立。
13.5 Floyd-Warshall 算法
核心思想：DP。dp[k][i][j] = 经过编号 ≤ k 的中间点，i 到 j 的最短路。
1 2 3 4 5 6 7 8 9 10 11 12 13 14
// Floyd-Warshall：多源最短路 voidfloyd(std::vector<std::vector<int>>& dist){ int n = dist.size(); // k: 中间点 for (int k = 0; k < n; ++k) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX) { dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]); } } } } }
Floyd 也能检测负权环：
1 2 3 4 5 6
// 如果 dist[i][i] < 0（i 到自己有负权环），则存在负权环 for (int i = 0; i < n; ++i) { if (dist[i][i] < 0) { // 存在负权环 } }
// Kruskal：使用并查集 structEdge { int u, v, w; booloperator<(const Edge& o) const { return w < o.w; } };
classUnionFind { std::vector<int> parent, rank_; public: UnionFind(int n) : parent(n), rank_(n, 0) { iota(parent.begin(), parent.end(), 0); } intfind(int x){ return parent[x] == x ? x : parent[x] = find(parent[x]); } boolunite(int x, int y){ x = find(x); y = find(y); if (x == y) returnfalse; if (rank_[x] < rank_[y]) std::swap(x, y); parent[y] = x; if (rank_[x] == rank_[y]) rank_[x]++; returntrue; } };
intkruskal(int n, std::vector<Edge>& edges){ std::sort(edges.begin(), edges.end()); UnionFind uf(n); int total = 0, count = 0; for (auto& e : edges) { if (uf.unite(e.u, e.v)) { total += e.w; count++; if (count == n - 1) break; } } return count == n - 1 ? total : -1; }
14.5 Prim vs Kruskal
维度
Prim
Kruskal
思想
加点
加边
数据结构
优先队列
并查集 + 排序
时间复杂度
O(E log V)
O(E log E)
适用图
稠密图
稀疏图
实现难度
中
中（含并查集）
边权重可相同
✅
✅
十五、拓扑排序
15.1 什么是拓扑序？
拓扑排序（Topological Sort）：DAG（有向无环图）中，将顶点排成线性序列，使得每条有向边 u→v，u 在 v 之前。
// 拓扑排序 - Kahn 算法 std::vector<int> topoSort(int n, const std::vector<std::vector<int>>& adj){ std::vector<int> indeg(n, 0); for (int u = 0; u < n; ++u) { for (int v : adj[u]) indeg[v]++; } std::queue<int> q; for (int i = 0; i < n; ++i) { if (indeg[i] == 0) q.push(i); } std::vector<int> order; while (!q.empty()) { int u = q.front(); q.pop(); order.push_back(u); for (int v : adj[u]) { if (--indeg[v] == 0) q.push(v); } } return order.size() == n ? order : std::vector<int>{}; // 空 = 有环 }
// 拓扑排序 - DFS 逆后序 voiddfsTopo(int u, const std::vector<std::vector<int>>& adj, std::vector<bool>& visited, std::stack<int>& stk){ visited[u] = true; for (int v : adj[u]) { if (!visited[v]) dfsTopo(v, adj, visited, stk); } stk.push(u); // 后序入栈 }
std::vector<int> topoSortDFS(int n, const std::vector<std::vector<int>>& adj){ std::vector<bool> visited(n, false); std::stack<int> stk; for (int i = 0; i < n; ++i) { if (!visited[i]) dfsTopo(i, adj, visited, stk); } std::vector<int> order; while (!stk.empty()) { order.push_back(stk.top()); stk.pop(); } return order; }
15.4 拓扑排序流程图
graph TD
A["计算所有节点入度"]
B["入度为 0 的入队"]
C["弹出队首 u，输出"]
D["遍历 u 邻居 v，--indeg[v]"]
E{"indeg[v]==0？"}
F["v 入队"]
G{"队列空？"}
H["✅ 结束"]
I["❌ 有环"]
A --> B --> C --> D --> E
E -->|"是"| F
F --> D
D -.->|"遍历完"| G
E -->|"否"| D
G -->|"否"| C
G -->|"是"| H
H -.->|"输出数 < n"| I
style A fill:#C7CEEA,stroke:#9FA8DA,color:#333
style B fill:#E8D5F5,stroke:#CE93D8,color:#333
style C fill:#FFDAB9,stroke:#FFAB76,color:#333
style D fill:#FFDAB9,stroke:#FFAB76,color:#333
style E fill:#FFF9C4,stroke:#F9A825,color:#333
style F fill:#B5EAD7,stroke:#80CBC4,color:#333
style G fill:#FFF9C4,stroke:#F9A825,color:#333
style H fill:#B5EAD7,stroke:#80CBC4,color:#333
style I fill:#FFB3C6,stroke:#F48FB1,color:#333
15.5 拓扑排序应用
场景
应用
课程选修
必须先修完 A 才能修 B
编译系统
Makefile 依赖、头文件顺序
任务调度
流水线调度
死锁检测
看环
十六、实战：手撕一个简化版红黑树
说明：完整红黑树代码量约 300 行，本节展示插入核心（约 80 行）。完整版可参考 Linux 5.x 内核 lib/rbtree.c。
16.1 节点定义
1 2 3 4 5 6 7 8 9
enumColor { RED, BLACK }; structRBNode { int key; Color color; RBNode* left, *right, *parent; RBNode(int k) : key(k), color(RED), left(nullptr), right(nullptr), parent(nullptr) {} };
intnumIslands(std::vector<std::vector<char>>& grid){ if (grid.empty()) return0; int m = grid.size(), n = grid[0].size(); int count = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == '1') { dfs(grid, i, j); count++; } } } return count; } voiddfs(std::vector<std::vector<char>>& grid, int i, int j){ int m = grid.size(), n = grid[0].size(); if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1') return; grid[i][j] = '0'; // 标记访问 dfs(grid, i+1, j); dfs(grid, i-1, j); dfs(grid, i, j+1); dfs(grid, i, j-1); }