二叉树算法#

递归三部曲：

1. 确定递归函数的参数和返回值
2. 确定终止条件
3. 确定单层递归的逻辑

二叉树的递归遍历：

1. 设置函数：void traversal(TreeNode* cur, vector<int>& vec)。第一个参数传入当前树节点，第二个参数传入输出的结果
2. 设置终止条件：cur == NULL 时 return，并输出函数值
3. 前序：先取值，使用 vec.push_back 来增长数组，再遍历左子树，在遍历右子树。中序和后序同理

二叉树的迭代遍历：

1. 设置 stack<TreeNode*> st 节点栈
2. 前序：将根节点推入栈中。如果栈非空，弹出栈顶元素读值，右左节点入栈，空节点不入栈
3. 中序：如果栈非空且当前节点非空，则先循环访问到最底层，同时把数据放入栈中。如果空了，则弹出栈顶元素，访问栈顶元素，并访问栈顶的右节点。 统一迭代法：空节点作为标记，右中 NULL 左入栈，遇到 NULL 先 pop 再访问再 pop。
4. 后序：由于先序遍历中左右，后序遍历左右中，则调换先序遍历的入栈顺序，并将结果反转，则可得到后续遍历。将根节点推入栈中。 如果栈非空，弹出栈顶元素读值，左右节点入栈，空节点不入栈，最后反转结果数组。

二叉树的层序遍历：非递归

1. 设置队列 queue<TreeNode*> que，将 root push 进队列中
2. 若队列非空，弹出队列顶端节点并访问，把左孩子和右孩子依次放入队列中。

线索化二叉树：

1. 设置 Ltag，Rtag，若 Ltag=0 则指向左孩子，=1 则指向前驱。Rtag 同理。
2. 线索化：全局变量 pre=刚才访问过的节点，初始化为 NULL。中序遍历。节点左指针非空则置为 link，否则置为 thread，右指针同理。若 pre 存在，pre 右 tag 是线索，则 pre 右指针域指向 p。P 左 tag 是线索，p 左指针域指向 pre
3. 找中序前驱：最左下的节点 or 线索节点
4. 中序线索树必有两个指针为空。前序最右孩子右指针空，后序最左孩子左指针空，只有一个节点时有两个空指针

DFS：深度优先遍历（先序）；BFS：广度优先遍历 广义上的后序遍历：先递归，后处理

翻转二叉树：

1. 函数 invertTree(TreeNode* root)，返回值 return *root
2. 当 root 为 NULL 时递归终止直接返回 root 节点
3. 交换左孩子和右孩子，然后递归翻转左孩子和右孩子。

对称二叉树：迭代，后序遍历，左右中=右左中；队列

1. 设置函数 bool compare(*left, *right)
2. 终止条件：左节点 != 右节点，return false，若两节点都空则 return true
3. 单层遍历：两节点非空且都有值：若 compare(*left->left, right->tight) 且 compare(*left->right, right->left) 为真则返回真。

• 求二叉树最大深度=求二叉树高度，递归左右子树，取最大值+1
• 求二叉树最小深度：min（左右子树最小深度）。有坑：若左子树为空右子树非空则深度为 1+右子树最小深度，而不是 1！
• 求最近公共祖先：
  1. 函数 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
  2. 终止条件：root = p 或 root = q 或 root = NULL 时返回 root
  3. 单层处理：后序遍历左子树，右子树的值存入 left，right。若都非空则该 root 就是最近公共祖先。若 left 是空则说明东西在右子树，返回 right 的值，right 是空则返回 left。

树和森林#

1. 森林=>二叉树：先把根串起来，然后左孩子右兄弟
2. 二叉树=>森林：将 x 的右孩子，右孩子的右孩子全部与节点相连，并去掉双亲连线。

哈夫曼树#

• 带权路径长度（WPL，Weighted Path Length）：$WPL=\sum_{i=1}^nw_{i}\times l_{i}$。哈夫曼树是二叉树中 WPL 最小的那个二叉树

构造哈夫曼树：

1. 若有 n 个节点，这是节点链表 tree[2n]，在 1-n 号位中填充节点。每一个节点有权值、父、左右孩子属性。初始父母左右孩子都是 0
2. 选取父节点不为 0，权值最小的两个节点（堆与优先队列实现），与新节点构建父子关联
3. 重复直到只剩一个节点

哈夫曼编码：前缀编码

平衡二叉树#

又称为 AVL（ Adelson-Velsky and Landis）树。左右子树高度差不超过一

中序+后序重建二叉树代码解释#

中序+后序重建二叉树思路

1. 使用 unordered_map 来保存中序遍历的节点值和序号，方便查找
2. 后序遍历最后一个元素是根节点，找到根节点的序号
3. 依照根节点序号 i，将元素分为 left to i-1、i+1 to right 两部分。并创建根节点。函数返回根节点
4. root->left 指向通过左子树构建的节点，右侧同理，递归下去
5. right>left ：返回 false。

中序+前序重建二叉树：前序序列第一个元素是根节点，其他照旧 核心原理：

用例子说明： 假设有这棵树：

1
        A
2
       / \
3
      B   C
4
     / \   \
5
    D   E   F

• 中序遍历: [D, B, E, A, F, C]
• 后序遍历: [D, E, B, F, C, A] 算法步骤图解：

1
第1步：后序最后一个 = A (根节点)
2
中序: [D, B, E, A, F, C]
3
              ↑
4
           找到A的位置
5

6
左子树中序: [D, B, E]     右子树中序: [F, C]
7
左子树后序: [D, E, B]     右子树后序: [F, C]
8

9
第2步：递归处理左子树 [D, B, E]
10
后序最后一个 = B (左子树的根)
11
...以此类推

代码逐行解释

1
BinaryTreeNode* BinaryTreeNode::buildTreeFromInorderPostorderHelper(
2
    const vector<string>& inorder, int inStart, int inEnd,      // 中序的范围
3
    const vector<string>& postorder, int postStart, int postEnd, // 后序的范围
4
    unordered_map<string, int>& inorderMap)                      // 快速查找用的映射
5
{
6
    // 1️⃣ 递归终止：范围无效时返回空
7
    if (postStart > postEnd || inStart > inEnd) {
8
        return nullptr;
9
    }
10

11
    // 2️⃣ 后序遍历的最后一个元素 = 当前子树的根
12
    string rootVal = postorder[postEnd];  // 例如第一次是 "A"
13
    BinaryTreeNode* root = new BinaryTreeNode();
14
    root->name = rootVal;
15

16
    // 3️⃣ 在中序遍历中找到根的位置，用于划分左右子树
17
    int inRoot = inorderMap[rootVal];  // "A" 在中序中的索引是 3
18
    int numsLeft = inRoot - inStart;   // 左子树节点数 = 3 - 0 = 3
19

20
    // 4️⃣ 递归构建左子树
21
    // 中序范围: [inStart, inRoot-1] → [0, 2] 即 [D, B, E]
22
    // 后序范围: [postStart, postStart+numsLeft-1] → [0, 2] 即 [D, E, B]
23
    root->left = buildTreeFromInorderPostorderHelper(
24
        inorder, inStart, inRoot - 1,
25
        postorder, postStart, postStart + numsLeft - 1,
26
        inorderMap);
27

28
    // 5️⃣ 递归构建右子树
29
    // 中序范围: [inRoot+1, inEnd] → [4, 5] 即 [F, C]
30
    // 后序范围: [postStart+numsLeft, postEnd-1] → [3, 4] 即 [F, C]
31
    root->right = buildTreeFromInorderPostorderHelper(
32
        inorder, inRoot + 1, inEnd,
33
        postorder, postStart + numsLeft, postEnd - 1,
34
        inorderMap);
35

36
    return root;
37
}

1. 后序末尾找根 - [postorder[postEnd(vscode-file://vscode-app/d:/Program%20Files%20(x86)/Microsoft%20VS%20Code/resources/app/out/vs/code/electron-browser/workbench/workbench. Html) 就是根
2. 中序定左右 - 根在中序中的位置把序列分成左右两部分
3. 计算左子树大小 - numsLeft = inRoot - inStart，这个数字用来划分后序序列
4. 递归处理 - 对左右子树分别递归，缩小范围

inorderMap 的作用是把 O (n) 的查找变成 O (1)，提高效率。

图的遍历#

回溯法：暴力搜索问题，遇到不对的状态或成功完成任务就回溯

1. 确认递归函数和参数
2. 确认终止条件和返回值：if ()，存放结果，return
3. 处理目前搜索节点出发的路径：for 剩余节点：处理节点、bfs、撤销当前步骤

深度优先搜索：DFS。如何用深度优先搜索出所有可达路径？

1. void dfs (const vector<vector<int>>& graph, int x, int n)，输入邻接矩阵，n 是终点，x 是目前遍历的点。二维数组存放所有路径 vector<vector<int>> result
2. 确认终止条件：当 x=n 时终止，路径 push_back 到二维数组
3. 处理目前搜索节点：遍历邻接矩阵第 x 行。如果 edge[x][i] == 1，则路径中添加该节点 path.push_back(i)，深度优先遍历 dfs (i)，再撤销改变 path.pop_back。

• 边的分类：树边、后向边、前向边、横向边

广度优先搜索：BFS。队列实现。跳过红父节点的访问 岛屿数量遍历：对于 $n\times n$ 方格 grid[n][n]，建立数组 visited[n][n]。遍历方格，对于一个没有访问过的陆地，计数器+1，并将该陆地周围全部遍历一遍；访问过的陆地和海洋直接跳过。

拓扑排序：选取入度为 0 的节点，记录并删除，递归直到没有节点

最小生成树#

最小生成树：建立 n-1 条边把图连起来

• Prim 算法：维护节点的集合
  1. 维护 minDist 数组，为剩余节点到最小生成树的最短距离。选择距离生成树最近的节点
  2. 最近节点加入生成树
  3. 更新 minDist 数组：
• Kruskal 算法：维护边的集合
  1. 排序边的权值
  2. 遍历排序后的边，若边首尾不在一个集合则加入，首尾在一个集合则忽略。使用并查集：
     1. 初始化 father[i]=i
     2. Find 函数与路径压缩：return u == father[u] ? u : father[u] = find(father[u]);
     3. Union 函数与按秩（树的高度）堆叠：小的放在大的下面

单源最短路径#

Dijkstra：源到目标点的最短路径。与 prim 类似：$O(E\log V)$ 或者 $O(V^2)$，未优化前：

1. 维护 minDist 和 visited 两个数组，选距离原点最近的未访问的节点（这一步可以用堆来优化）
2. 标记该节点已访问过
3. 从该节点出发遍历所有邻接边，更新未访问节点到源点的距离

Bellman-ford 算法：源到目标点最短路径：$O(EV)$

1. 创建 dist[] 距离数组，源点距离为 0，其余为无穷大。数组长度为 V
2. 循环 V-1 次。每次循环中都遍历 E 条边，每条边有权值 w (u, v)：如果 dist[u] + w(u,v) < dist[v]，则更新 dist[v] = dist[u] + w(u,v) 。
3. 负环检测：在第 V 次循环时，若发现还有节点被更新，则存在负环，将所有距离设为-1.

上述算法在计网U5-控制平面中用于选路。 A*

所有节点对最短路径#

Floyd：grid[i][j][k] = min(grid[i][k][k - 1] + grid[k][j][k - 1]， grid[i][j][k - 1])

最大流#

最大流最小切割定理：网络最大值=最小切割的容量 Ford-fulkson 方法：

1. 初始化流 f 为 0
2. 构建残存网络：前向边（残存容量 c-f）、反向边（可以反向流量 f）
3. 寻找增广路径：找到 s 到 t 的简单路径，找到瓶颈容量
4. 更新流量
5. 重复，直到残存网络找不到 s 到 t 的路径

Edmonds-Karp 算法：规定使用 FF 方法时，必须使用 BFS 来寻找增广路径。复杂度 $O(VE^2)$。