数据结构实验复习整理

依据：

• 数据结构实验-复习提纲-2025级.pptx：考试两题，每题 50 分；重点是图、树；允许使用 STL，尤其要熟练 stack、queue。复习提纲全文将贴在本文最后。
• 实验作业/Week1 到 Week10：前期线性表/栈队列/递归，后期树与图综合题。
• 板子：补充树、图、并查集、堆、排序二分等模板。

0. 考前必须背的清单

优先级最高：

1. 图：邻接表建图、邻接矩阵建图、DFS、BFS、迷宫/网格搜索、无权最短路、路径长度计算。
2. 树：二叉树节点定义、递归遍历、迭代遍历、层序遍历、由输入构造树、由前序+中序重建树、树高/深度/宽度/路径长度。
3. 辅助结构：stack、queue、priority_queue、unordered_map、vector。

次重点：

1. 并查集 + Kruskal 最小生成树。
2. Dijkstra、Floyd。
3. 拓扑排序、二分图染色、克隆图。
4. 链表、单调栈、二分、堆、排序。

考试写代码的建议：

• 默认用 C++，开头写：

#include <bits/stdc++.h>
using namespace std;

• 点编号如果题目是 1..n，数组开 n + 1；如果是 0..n-1，数组开 n。
• BFS 求最短步数时，dist 初始化为 -1；Dijkstra/Floyd 求最短路时，不可达用大数 INF。
• 树题先写节点结构和构造函数，再写遍历/计算函数。
• 题目定义非标准概念时，先把样例含义翻译成“遍历顺序/层数/距离/计数条件”，再写代码。

1. STL 必背

1.1 栈 stack

stack<int> st;
st.push(x);
st.pop();
int x = st.top();
bool ok = st.empty();

常见用途：

• 括号匹配。
• 中缀转后缀、表达式求值。
• 模拟递归。
• DFS 的迭代写法。
• 单调栈。

1.2 队列 queue

queue<int> q;
q.push(x);
q.pop();
int x = q.front();
bool ok = q.empty();

常见用途：

• 图的 BFS。
• 树的层序遍历。
• 迷宫最短路。
• 拓扑排序。

1.3 优先队列 priority_queue

priority_queue<int> big; // 大根堆
priority_queue<int, vector<int>, greater<int>> small; // 小根堆

priority_queue<pair<long long, int>,
               vector<pair<long long, int>>,
               greater<pair<long long, int>>> pq; // Dijkstra

1.4 哈希表 unordered_map / unordered_set

unordered_map<int, int> cnt;
cnt[x]++;
if (cnt.count(x)) {}

unordered_set<int> vis;
vis.insert(x);
if (vis.count(x)) {}

2. 图算法

PPT 明确说明：第一题可能考用图解决实际问题，包括图的构建、存储、遍历、路径长度计算；迷宫问题要重点研究。

2.1 邻接表建图

考试快速实现优先背 vector<vector<>> 版：每个顶点对应一个 vector，里面存它连出去的边。

struct Edge {
    int to;
    int w;
};

int n, m;
vector<vector<Edge>> g;

void initGraph(int n_) {
    n = n_;
    g.assign(n + 1, {});
}

void addUndirected(int u, int v, int w = 1) {
    g[u].push_back({v, w});
    g[v].push_back({u, w});
}

void addDirected(int u, int v, int w = 1) {
    g[u].push_back({v, w});
}

无权图可以更短：

vector<vector<int>> g(n + 1);
g[u].push_back(v);
g[v].push_back(u);

课程式链表邻接表也要会看会写。它是“顶点表 + 边结点链表”：每个顶点有一个 first 指针，指向它的第一条边；每条边结点保存邻接点下标、权值、下一条边指针。

const int MAXV = 1005;

struct ArcNode {
    int adjvex;        // 这条边指向的顶点下标
    int weight;        // 边权；无权图可统一写 1
    ArcNode* next;     // 下一条边
};

struct VNode {
    int data;          // 顶点信息；如果顶点就是编号，可存 i
    ArcNode* first;    // 第一条边
};

struct ALGraph {
    VNode vertices[MAXV];
    int vexnum, arcnum;
    bool directed;
};

void initGraph(ALGraph& G, int n, bool directed = false) {
    G.vexnum = n;
    G.arcnum = 0;
    G.directed = directed;
    for (int i = 1; i <= n; i++) {
        G.vertices[i].data = i;
        G.vertices[i].first = nullptr;
    }
}

void addArc(ALGraph& G, int u, int v, int w = 1) {
    ArcNode* p = new ArcNode{v, w, G.vertices[u].first};
    G.vertices[u].first = p;
}

void addEdge(ALGraph& G, int u, int v, int w = 1) {
    addArc(G, u, v, w);
    if (!G.directed) addArc(G, v, u, w);
    G.arcnum++;
}

链表邻接表的遍历写法：

for (ArcNode* p = G.vertices[u].first; p != nullptr; p = p->next) {
    int v = p->adjvex;
    int w = p->weight;
}

2.2 邻接矩阵建图

适合点数小、需要直接查询两点是否相连/边权的题。

const long long INF = (1LL << 60);
int n, m;
vector<vector<long long>> mat;

void initMatrix(int n_) {
    n = n_;
    mat.assign(n + 1, vector<long long>(n + 1, INF));
    for (int i = 1; i <= n; i++) mat[i][i] = 0;
}

void addEdge(int u, int v, long long w, bool undirected = true) {
    mat[u][v] = min(mat[u][v], w);
    if (undirected) mat[v][u] = min(mat[v][u], w);
}

2.3 DFS：连通性、遍历、计数

链表邻接表递归 DFS：

int visited[MAXV];

void dfs(ALGraph& G, int u) {
    visited[u] = 1;
    for (ArcNode* p = G.vertices[u].first; p != nullptr; p = p->next) {
        int v = p->adjvex;
        if (!visited[v]) dfs(G, v);
    }
}

判断两个点是否连通：

bool connected(ALGraph& G, int s, int t) {
    memset(visited, 0, sizeof(visited));
    dfs(G, s);
    return visited[t];
}

链表邻接表迭代 DFS：

void dfsIter(ALGraph& G, int s) {
    memset(visited, 0, sizeof(visited));
    stack<int> st;
    st.push(s);

    while (!st.empty()) {
        int u = st.top();
        st.pop();
        if (visited[u]) continue;
        visited[u] = 1;

        for (ArcNode* p = G.vertices[u].first; p != nullptr; p = p->next) {
            int v = p->adjvex;
            if (!visited[v]) st.push(v);
        }
    }
}

2.4 BFS：无权最短路/层数

最常考。第一次到达某点时，距离就是最短步数。

vector<int> bfsDist(ALGraph& G, int s) {
    vector<int> dist(G.vexnum + 1, -1);
    queue<int> q;
    dist[s] = 0;
    q.push(s);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (ArcNode* p = G.vertices[u].first; p != nullptr; p = p->next) {
            int v = p->adjvex;
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist;
}

如果还要输出路径，记录前驱：

vector<int> bfsPath(ALGraph& G, int s, int t) {
    vector<int> dist(G.vexnum + 1, -1);
    vector<int> pre(G.vexnum + 1, -1);
    queue<int> q;
    dist[s] = 0;
    q.push(s);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (u == t) break;
        for (ArcNode* p = G.vertices[u].first; p != nullptr; p = p->next) {
            int v = p->adjvex;
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                pre[v] = u;
                q.push(v);
            }
        }
    }

    vector<int> path;
    if (dist[t] == -1) return path;
    for (int x = t; x != -1; x = pre[x]) path.push_back(x);
    reverse(path.begin(), path.end());
    return path;
}

2.5 迷宫/网格 BFS

适合“用图解决实际问题”。把每个格子当作点，上下左右是边。

struct Node {
    int x, y;
};

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int shortestMaze(vector<string>& a, int sx, int sy, int tx, int ty) {
    int n = a.size(), m = a[0].size();
    vector<vector<int>> dist(n, vector<int>(m, -1));
    queue<Node> q;

    if (a[sx][sy] == '#' || a[tx][ty] == '#') return -1;
    dist[sx][sy] = 0;
    q.push({sx, sy});

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        if (x == tx && y == ty) return dist[x][y];
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (a[nx][ny] == '#') continue;
            if (dist[nx][ny] != -1) continue;
            dist[nx][ny] = dist[x][y] + 1;
            q.push({nx, ny});
        }
    }
    return -1;
}

输出迷宫路径：

vector<Node> restoreMazePath(vector<vector<Node>>& pre, int sx, int sy, int tx, int ty) {
    vector<Node> path;
    for (int x = tx, y = ty; !(x == -1 && y == -1); ) {
        path.push_back({x, y});
        if (x == sx && y == sy) break;
        Node p = pre[x][y];
        x = p.x;
        y = p.y;
    }
    reverse(path.begin(), path.end());
    return path;
}

2.6 Dijkstra：非负权单源最短路

边权不能为负。适合“从一个起点到其他所有点的最短距离”，例如网络延迟时间。

必背思路：

• dist[i]：从起点到 i 的当前最短距离。
• visited[i]：i 的最短距离是否已经确定。
• 小根堆每次取出当前距离最小的点，再用它更新相邻点。

注：因为小根堆每次弹出来的都是当前距离最小的点，所以一个点第一次从堆里弹出时，它的最短距离就已经确定了。

比如我们先发现，到这个点的距离是 10，后来又发现到这个点的距离是 5，这两个都会进堆，而小根堆会先弹出距离为 5 的那个，并将这个点标记为 visited，之后距离为 10 的记录弹出来时就可以直接跳过。

const long long INF = (1LL << 60);

vector<long long> dijkstra(int s) {
    int n = (int)g.size() - 1;
    vector<long long> dist(n + 1, INF);
    vector<bool> visited(n + 1, false);
    priority_queue<pair<long long, int>,
                   vector<pair<long long, int>>,
                   greater<pair<long long, int>>> pq;

    dist[s] = 0;
    pq.push({0, s});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (visited[u]) continue;
        visited[u] = true;

        for (auto e : g[u]) {
            int v = e.to;
            long long w = e.w;
            if (!visited[v] && dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

2.7 Floyd：任意两点最短路

适合 n 较小、需要多次查询任意两点距离。

void floyd(vector<vector<long long>>& d) {
    int n = (int)d.size() - 1;
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            if (d[i][k] >= INF) continue;
            for (int j = 1; j <= n; j++) {
                if (d[k][j] >= INF) continue;
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

2.8 并查集 DSU

用于连通性维护、Kruskal、朋友圈/连通分量。

考试和刷题优先背这个版本：parent + find + unite 返回 bool。

• find(x)：找 x 所在集合的代表节点，顺手路径压缩。
• unite(a, b)：合并两个集合；如果本来就在同一集合，返回 false。
• same(a, b)：判断两个点是否已经连通。

class UnionFind {
public:
    vector<int> parent;

    UnionFind(int n) {
        parent.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    bool unite(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);

        if (rootA == rootB) {
            return false;
        }

        parent[rootA] = rootB;
        return true;
    }

    bool same(int a, int b) {
        return find(a) == find(b);
    }
};

注意：如果题目点编号是 1..n，就写 UnionFind uf(n + 1);；如果编号是 0..n-1，就写 UnionFind uf(n);。

unite 返回 false 特别适合判断成环。例如一条边的两个端点已经连通，再连这条边就会成环。

2.9 Kruskal：最小生成树

只适用于无向连通图；如果最后选边数不是 n - 1，说明图不连通。

struct E {
    int u, v;
    long long w;
};

long long kruskal(int n, vector<E>& edges) {
    sort(edges.begin(), edges.end(), [](const E& a, const E& b) {
        return a.w < b.w;
    });

    UnionFind dsu(n + 1);
    long long ans = 0;
    int used = 0;

    for (auto e : edges) {
        if (dsu.unite(e.u, e.v)) {
            ans += e.w;
            used++;
            if (used == n - 1) break;
        }
    }

    if (used != n - 1) return -1;
    return ans;
}

2.10 拓扑排序

作业中出现过课程表。适合有向无环图、前置依赖。

vector<int> topoSort(int n, vector<vector<int>>& g, vector<int>& indeg) {
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (indeg[i] == 0) q.push(i);
    }

    vector<int> order;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        order.push_back(u);
        for (int v : g[u]) {
            if (--indeg[v] == 0) q.push(v);
        }
    }
    return order;
}

判断能否完成所有课程：

bool canFinish(int n, vector<vector<int>>& g, vector<int>& indeg) {
    return (int)topoSort(n, g, indeg).size() == n;
}

2.11 二分图染色

相邻点颜色必须不同。

bool isBipartite(vector<vector<int>>& g) {
    int n = g.size();
    vector<int> color(n, 0);

    function<bool(int, int)> dfs = [&](int u, int c) {
        color[u] = c;
        for (int v : g[u]) {
            if (color[v] == c) return false;
            if (color[v] == 0 && !dfs(v, -c)) return false;
        }
        return true;
    };

    for (int i = 0; i < n; i++) {
        if (color[i] == 0 && !dfs(i, 1)) return false;
    }
    return true;
}

2.12 克隆图

图节点带指针时，用哈希表保存“原节点 -> 新节点”。

struct Node {
    int val;
    vector<Node*> neighbors;
    Node(int v = 0) : val(v) {}
};

Node* cloneGraph(Node* node) {
    if (!node) return nullptr;

    unordered_map<Node*, Node*> mp;
    queue<Node*> q;
    mp[node] = new Node(node->val);
    q.push(node);

    while (!q.empty()) {
        Node* u = q.front();
        q.pop();
        for (Node* v : u->neighbors) {
            if (!mp.count(v)) {
                mp[v] = new Node(v->val);
                q.push(v);
            }
            mp[u]->neighbors.push_back(mp[v]);
        }
    }
    return mp[node];
}

3. 树算法

PPT 明确说明：第二题可能考树的重构、遍历、树中路径长度、二叉树宽度等。

3.1 二叉树节点

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v = 0) : val(v), left(nullptr), right(nullptr) {}
};

3.2 递归遍历

void preorder(TreeNode* root) {
    if (!root) return;
    cout << root->val << ' ';
    preorder(root->left);
    preorder(root->right);
}

void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->val << ' ';
    inorder(root->right);
}

void postorder(TreeNode* root) {
    if (!root) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->val << ' ';
}

3.3 迭代中序遍历

BST 第 K 小、BST 众数等题常用。

vector<int> inorderIter(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> st;
    TreeNode* cur = root;

    while (cur || !st.empty()) {
        while (cur) {
            st.push(cur);
            cur = cur->left;
        }
        cur = st.top();
        st.pop();
        res.push_back(cur->val);
        cur = cur->right;
    }
    return res;
}

3.4 层序遍历

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if (!root) return res;

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        int sz = q.size();
        vector<int> level;
        while (sz--) {
            TreeNode* u = q.front();
            q.pop();
            level.push_back(u->val);
            if (u->left) q.push(u->left);
            if (u->right) q.push(u->right);
        }
        res.push_back(level);
    }
    return res;
}

3.5 层序数组建树

输入类似：1 2 3 null 4。

TreeNode* buildLevel(const vector<string>& a) {
    if (a.empty() || a[0] == "null") return nullptr;

    TreeNode* root = new TreeNode(stoi(a[0]));
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;

    while (!q.empty() && i < (int)a.size()) {
        TreeNode* u = q.front();
        q.pop();

        if (i < (int)a.size() && a[i] != "null") {
            u->left = new TreeNode(stoi(a[i]));
            q.push(u->left);
        }
        i++;

        if (i < (int)a.size() && a[i] != "null") {
            u->right = new TreeNode(stoi(a[i]));
            q.push(u->right);
        }
        i++;
    }
    return root;
}

3.6 前序 + 中序重建二叉树

前序第一个是根；中序根左边是左子树，右边是右子树。

TreeNode* buildFromPreIn(vector<int>& pre, vector<int>& in) {
    unordered_map<int, int> pos;
    for (int i = 0; i < (int)in.size(); i++) pos[in[i]] = i;
    int pi = 0;

    function<TreeNode*(int, int)> build = [&](int L, int R) -> TreeNode* {
        if (L > R) return nullptr;
        int rootVal = pre[pi++];
        TreeNode* root = new TreeNode(rootVal);
        int mid = pos[rootVal];
        root->left = build(L, mid - 1);
        root->right = build(mid + 1, R);
        return root;
    };

    return build(0, (int)in.size() - 1);
}

3.7 含空标记的前序重建

如果输入是 DFS 序列，空节点用 # 或 null 表示，直接递归读。

TreeNode* buildPreWithNull(vector<string>& a, int& i) {
    if (i >= (int)a.size()) return nullptr;
    string s = a[i++];
    if (s == "#" || s == "null") return nullptr;

    TreeNode* root = new TreeNode(stoi(s));
    root->left = buildPreWithNull(a, i);
    root->right = buildPreWithNull(a, i);
    return root;
}

3.8 树高、节点数、叶子数

int height(TreeNode* root) {
    if (!root) return 0;
    return max(height(root->left), height(root->right)) + 1;
}

int countNodes(TreeNode* root) {
    if (!root) return 0;
    return countNodes(root->left) + countNodes(root->right) + 1;
}

int countLeaves(TreeNode* root) {
    if (!root) return 0;
    if (!root->left && !root->right) return 1;
    return countLeaves(root->left) + countLeaves(root->right);
}

3.9 二叉树宽度

如果题目定义“每层节点数最大值”为宽度：

int widthByCount(TreeNode* root) {
    if (!root) return 0;
    queue<TreeNode*> q;
    q.push(root);
    int ans = 0;

    while (!q.empty()) {
        int sz = q.size();
        ans = max(ans, sz);
        while (sz--) {
            TreeNode* u = q.front();
            q.pop();
            if (u->left) q.push(u->left);
            if (u->right) q.push(u->right);
        }
    }
    return ans;
}

如果题目定义“按完全二叉树位置编号，最右编号 - 最左编号 + 1”为宽度：

int widthByIndex(TreeNode* root) {
    if (!root) return 0;
    queue<pair<TreeNode*, unsigned long long>> q;
    q.push({root, 1});
    unsigned long long ans = 0;

    while (!q.empty()) {
        int sz = q.size();
        unsigned long long base = q.front().second;
        unsigned long long first = 0, last = 0;

        for (int i = 0; i < sz; i++) {
            auto [u, id] = q.front();
            q.pop();
            id -= base;
            if (i == 0) first = id;
            if (i == sz - 1) last = id;
            if (u->left) q.push({u->left, id * 2});
            if (u->right) q.push({u->right, id * 2 + 1});
        }
        ans = max(ans, last - first + 1);
    }
    return (int)ans;
}

3.10 路径长度、根到叶路径

根到某节点距离：

bool findPath(TreeNode* root, int target, vector<int>& path) {
    if (!root) return false;
    path.push_back(root->val);
    if (root->val == target) return true;
    if (findPath(root->left, target, path) || findPath(root->right, target, path)) return true;
    path.pop_back();
    return false;
}

所有根到叶路径：

void allRootToLeaf(TreeNode* root, vector<int>& path, vector<vector<int>>& ans) {
    if (!root) return;
    path.push_back(root->val);
    if (!root->left && !root->right) {
        ans.push_back(path);
    } else {
        allRootToLeaf(root->left, path, ans);
        allRootToLeaf(root->right, path, ans);
    }
    path.pop_back();
}

树的直径，也就是任意两点最长路径边数：

int diameter(TreeNode* root) {
    int ans = 0;
    function<int(TreeNode*)> h = [&](TreeNode* u) {
        if (!u) return 0;
        int L = h(u->left);
        int R = h(u->right);
        ans = max(ans, L + R);
        return max(L, R) + 1;
    };
    h(root);
    return ans;
}

3.11 平衡二叉树

bool isBalanced(TreeNode* root) {
    function<int(TreeNode*)> h = [&](TreeNode* u) {
        if (!u) return 0;
        int L = h(u->left);
        if (L == -1) return -1;
        int R = h(u->right);
        if (R == -1) return -1;
        if (abs(L - R) > 1) return -1;
        return max(L, R) + 1;
    };
    return h(root) != -1;
}

3.12 对称二叉树

bool isMirror(TreeNode* a, TreeNode* b) {
    if (!a && !b) return true;
    if (!a || !b) return false;
    if (a->val != b->val) return false;
    return isMirror(a->left, b->right) && isMirror(a->right, b->left);
}

bool isSymmetric(TreeNode* root) {
    return !root || isMirror(root->left, root->right);
}

3.13 最近公共祖先 LCA

树上路径距离题经常用。

TreeNode* lca(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode* L = lca(root->left, p, q);
    TreeNode* R = lca(root->right, p, q);
    if (L && R) return root;
    return L ? L : R;
}

节点到目标值的深度：

int depthOf(TreeNode* root, int target, int dep = 0) {
    if (!root) return -1;
    if (root->val == target) return dep;
    int L = depthOf(root->left, target, dep + 1);
    if (L != -1) return L;
    return depthOf(root->right, target, dep + 1);
}

3.14 距离目标节点 K 的所有节点

Week9 出现过类似题。做法：树转无向图，再 BFS。

void buildGraph(TreeNode* root, unordered_map<TreeNode*, vector<TreeNode*>>& g) {
    if (!root) return;
    if (root->left) {
        g[root].push_back(root->left);
        g[root->left].push_back(root);
        buildGraph(root->left, g);
    }
    if (root->right) {
        g[root].push_back(root->right);
        g[root->right].push_back(root);
        buildGraph(root->right, g);
    }
}

vector<int> distanceK(TreeNode* target, int k, unordered_map<TreeNode*, vector<TreeNode*>>& g) {
    vector<int> ans;
    unordered_set<TreeNode*> vis;
    queue<pair<TreeNode*, int>> q;
    q.push({target, 0});
    vis.insert(target);

    while (!q.empty()) {
        auto [u, d] = q.front();
        q.pop();
        if (d == k) {
            ans.push_back(u->val);
            continue;
        }
        for (TreeNode* v : g[u]) {
            if (!vis.count(v)) {
                vis.insert(v);
                q.push({v, d + 1});
            }
        }
    }
    sort(ans.begin(), ans.end());
    return ans;
}

4. 栈、队列与递归题

4.1 单调栈：右侧第一个更大元素

vector<int> nextGreaterRight(vector<int>& a) {
    int n = a.size();
    vector<int> nxt(n, -1);
    stack<int> st; // 下标，保持栈内值单调递减

    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && a[st.top()] <= a[i]) st.pop();
        if (!st.empty()) nxt[i] = st.top();
        st.push(i);
    }
    return nxt;
}

4.2 柱状图最大矩形

Week2 重点题。

long long largestRectangleArea(vector<int>& h) {
    h.push_back(0);
    stack<int> st;
    long long ans = 0;

    for (int i = 0; i < (int)h.size(); i++) {
        while (!st.empty() && h[st.top()] > h[i]) {
            int height = h[st.top()];
            st.pop();
            int left = st.empty() ? -1 : st.top();
            int width = i - left - 1;
            ans = max(ans, 1LL * height * width);
        }
        st.push(i);
    }
    h.pop_back();
    return ans;
}

4.3 出栈序列是否合法

bool validPopSeq(vector<int>& in, vector<int>& out) {
    stack<int> st;
    int j = 0;
    for (int x : in) {
        st.push(x);
        while (!st.empty() && j < (int)out.size() && st.top() == out[j]) {
            st.pop();
            j++;
        }
    }
    return j == (int)out.size();
}

4.4 中缀转后缀

int priority(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

bool isOp(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

string infixToPostfix(const string& s) {
    string out;
    stack<char> ops;

    for (char c : s) {
        if (isdigit(c)) {
            out += c;
        } else if (c == '(') {
            ops.push(c);
        } else if (c == ')') {
            while (!ops.empty() && ops.top() != '(') {
                out += ops.top();
                ops.pop();
            }
            if (!ops.empty()) ops.pop();
        } else if (isOp(c)) {
            while (!ops.empty() && priority(ops.top()) >= priority(c)) {
                out += ops.top();
                ops.pop();
            }
            ops.push(c);
        }
    }

    while (!ops.empty()) {
        out += ops.top();
        ops.pop();
    }
    return out;
}

5. 链表

5.1 单链表节点

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int v = 0) : val(v), next(nullptr) {}
};

5.2 尾插建表

ListNode* buildList(vector<int>& a) {
    ListNode dummy;
    ListNode* tail = &dummy;
    for (int x : a) {
        tail->next = new ListNode(x);
        tail = tail->next;
    }
    return dummy.next;
}

5.3 反转链表

ListNode* reverseList(ListNode* head) {
    ListNode* pre = nullptr;
    while (head) {
        ListNode* nxt = head->next;
        head->next = pre;
        pre = head;
        head = nxt;
    }
    return pre;
}

5.4 快慢指针判环

bool hasCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

5.5 倒数第 K 个节点

ListNode* kthFromEnd(ListNode* head, int k) {
    ListNode *fast = head, *slow = head;
    while (k-- && fast) fast = fast->next;
    if (k >= 0) return nullptr;
    while (fast) {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

5.6 合并两个有序链表

ListNode* mergeTwo(ListNode* a, ListNode* b) {
    ListNode dummy;
    ListNode* tail = &dummy;
    while (a && b) {
        if (a->val <= b->val) {
            tail->next = a;
            a = a->next;
        } else {
            tail->next = b;
            b = b->next;
        }
        tail = tail->next;
    }
    tail->next = a ? a : b;
    return dummy.next;
}

5.7 链表归并排序

Week10 出现过。

ListNode* sortList(ListNode* head) {
    if (!head || !head->next) return head;

    ListNode *slow = head, *fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    ListNode* mid = slow->next;
    slow->next = nullptr;

    ListNode* left = sortList(head);
    ListNode* right = sortList(mid);
    return mergeTwo(left, right);
}

6. 排序、二分、哈希、双指针

6.1 自定义排序

sort(v.begin(), v.end(), [](const auto& a, const auto& b) {
    if (a.second != b.second) return a.second < b.second;
    return a.first < b.first;
});

6.2 二分：第一个大于等于 x

int lowerBound(vector<int>& a, int x) {
    int l = 0, r = a.size();
    while (l < r) {
        int m = l + (r - l) / 2;
        if (a[m] >= x) r = m;
        else l = m + 1;
    }
    return l;
}

常见变形：

• 第一个 > x：条件改成 a[m] > x。
• 最后一个 < x：找第一个 >= x，答案 pos - 1。
• 最后一个 <= x：找第一个 > x，答案 pos - 1。
• 答案二分：把判断写成 bool check(mid)，找第一个满足的位置。

6.3 两数之和

pair<int, int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> pos;
    for (int i = 0; i < (int)nums.size(); i++) {
        int need = target - nums[i];
        if (pos.count(need)) return {pos[need], i};
        pos[nums[i]] = i;
    }
    return {-1, -1};
}

6.4 滑动窗口

int longestWindow(string s, int k) {
    vector<int> cnt(26, 0);
    int l = 0, ans = 0, maxFreq = 0;

    for (int r = 0; r < (int)s.size(); r++) {
        maxFreq = max(maxFreq, ++cnt[s[r] - 'A']);
        while (r - l + 1 - maxFreq > k) {
            cnt[s[l] - 'A']--;
            l++;
        }
        ans = max(ans, r - l + 1);
    }
    return ans;
}

6.5 双指针接雨水

long long trap(vector<int>& h) {
    int l = 0, r = (int)h.size() - 1;
    int lmax = 0, rmax = 0;
    long long ans = 0;

    while (l <= r) {
        if (lmax <= rmax) {
            lmax = max(lmax, h[l]);
            ans += max(0, lmax - h[l]);
            l++;
        } else {
            rmax = max(rmax, h[r]);
            ans += max(0, rmax - h[r]);
            r--;
        }
    }
    return ans;
}

7. 堆

优先使用 STL：

priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;

手写最小堆：

struct MinHeap {
    vector<int> a;

    bool cmp(int x, int y) {
        return x < y;
    }

    void siftUp(int i) {
        while (i > 0) {
            int p = (i - 1) / 2;
            if (cmp(a[p], a[i])) break;
            swap(a[p], a[i]);
            i = p;
        }
    }

    void siftDown(int i) {
        int n = a.size();
        while (true) {
            int l = i * 2 + 1;
            int r = i * 2 + 2;
            int best = i;
            if (l < n && !cmp(a[best], a[l])) best = l;
            if (r < n && !cmp(a[best], a[r])) best = r;
            if (best == i) break;
            swap(a[i], a[best]);
            i = best;
        }
    }

    void build(vector<int> v) {
        a = v;
        for (int i = (int)a.size() / 2 - 1; i >= 0; i--) siftDown(i);
    }

    void push(int x) {
        a.push_back(x);
        siftUp(a.size() - 1);
    }

    int top() {
        return a[0];
    }

    void pop() {
        if (a.empty()) return;
        a[0] = a.back();
        a.pop_back();
        if (!a.empty()) siftDown(0);
    }
};

注意：r = i * 2 + 2，不要写成 r = r * 2 + 2。

8. 常见输入处理

8.1 读一行空格分隔整数

vector<int> readIntsLine() {
    string line;
    getline(cin, line);
    stringstream ss(line);
    vector<int> a;
    int x;
    while (ss >> x) a.push_back(x);
    return a;
}

如果前面用过 cin >> n，再读整行前要吃掉换行：

cin.ignore(numeric_limits<streamsize>::max(), '\n');

8.2 读 null 树数组

vector<string> readTokensLine() {
    string line;
    getline(cin, line);
    stringstream ss(line);
    vector<string> a;
    string s;
    while (ss >> s) a.push_back(s);
    return a;
}

8.3 图输入模板

链表邻接表输入：

int n, m;
cin >> n >> m;
ALGraph G;
initGraph(G, n, false);

for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    addEdge(G, u, v);
}

带权图：

int n, m;
cin >> n >> m;
ALGraph G;
initGraph(G, n, false);

for (int i = 0; i < m; i++) {
    int u, v;
    int w;
    cin >> u >> v >> w;
    addEdge(G, u, v, w);
}

9. 按周作业主题回顾

• Week1：线性表、链表、哈希两数之和、约瑟夫环、倒数第 K 个节点。
• Week2：栈、最大矩形、出栈序列、迷宫路径、中缀/后缀表达式、递归模拟。
• Week3：队列、循环队列、前缀和、单调队列/窗口、排序。
• Week4：递归、链表逆序输出、回文、异位词分组、回溯。
• Week5：二叉树 DFS、遍历、树结构转换、目标节点相关路径。
• Week6：层序建树、中序遍历、树路径最大和、BST 子树、重建树。
• Week7：图的 DFS、连通性、邻接表/邻接矩阵、Kruskal、单词变换。
• Week8：并查集、图遍历、课程表拓扑排序、动态规划/综合题。
• Week9：树转图、距离 K、并查集、最大概率路径、树 DFS。
• Week10：链表归并排序、二分图、克隆图、数组/字符串综合。

10. 图题骨架

#include <bits/stdc++.h>
using namespace std;

const int MAXV = 1005;

struct ArcNode {
    int adjvex;
    int weight;
    ArcNode* next;
};

struct VNode {
    int data;
    ArcNode* first;
};

struct ALGraph {
    VNode vertices[MAXV];
    int vexnum, arcnum;
    bool directed;
};

void initGraph(ALGraph& G, int n, bool directed = false) {
    G.vexnum = n;
    G.arcnum = 0;
    G.directed = directed;
    for (int i = 1; i <= n; i++) {
        G.vertices[i].data = i;
        G.vertices[i].first = nullptr;
    }
}

void addArc(ALGraph& G, int u, int v, int w = 1) {
    ArcNode* p = new ArcNode{v, w, G.vertices[u].first};
    G.vertices[u].first = p;
}

void addEdge(ALGraph& G, int u, int v, int w = 1) {
    addArc(G, u, v, w);
    if (!G.directed) addArc(G, v, u, w);
    G.arcnum++;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    ALGraph G;
    initGraph(G, n, false);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        addEdge(G, u, v);
    }

    vector<int> dist(n + 1, -1);
    queue<int> q;
    int s = 1;
    dist[s] = 0;
    q.push(s);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (ArcNode* p = G.vertices[u].first; p != nullptr; p = p->next) {
            int v = p->adjvex;
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }

    return 0;
}

11. 树题骨架

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v = 0) : val(v), left(nullptr), right(nullptr) {}
};

TreeNode* buildLevel(vector<string>& a) {
    if (a.empty() || a[0] == "null") return nullptr;
    TreeNode* root = new TreeNode(stoi(a[0]));
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;

    while (!q.empty() && i < (int)a.size()) {
        TreeNode* u = q.front();
        q.pop();
        if (i < (int)a.size() && a[i] != "null") {
            u->left = new TreeNode(stoi(a[i]));
            q.push(u->left);
        }
        i++;
        if (i < (int)a.size() && a[i] != "null") {
            u->right = new TreeNode(stoi(a[i]));
            q.push(u->right);
        }
        i++;
    }
    return root;
}

int height(TreeNode* root) {
    if (!root) return 0;
    return max(height(root->left), height(root->right)) + 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string line, s;
    getline(cin, line);
    stringstream ss(line);
    vector<string> a;
    while (ss >> s) a.push_back(s);

    TreeNode* root = buildLevel(a);
    cout << height(root) << '\n';
    return 0;
}

12. 复习提纲全文

1. 考察用图结构解决实际问题。所考察的内容涉及但不限于：图的构建（从输入数据构建图结构）、图的存储结构、图的遍历（如深度优先遍历或广度优先遍历）、路径长度计算等。建议仔细研究用图解决迷宫问题等示例代码。
2. 考察树的重构以及树结构上的相关算法。所考察的内容涉及但不限于：树的重构（例如根据深度优先遍历序列构造树）、树的遍历（前序遍历、中序遍历、后序遍历）、树中的路径长度的计算等。建议仔细研究教材中关于求二叉树的宽度的示例代码。
3. 用递归方式或迭代方式构造算法。正确使用栈或者队列作为辅助数据结构。
4. 为了加速实现过程，允许直接使用STL中的类进行编程。最重要的两个类是：std::stack和std::queue。由于这两个类本质上都是类模板，所以要提前练习如何使用它们。否则，就需要手动构建栈或者队列的相关代码，会极大延缓答题进程。
5. 为了出题的需要，会定义一些非标准概念，如二叉树的宽度等等。这些概念会在题目中被详细描述并给出具体示例，请务必根据示例清楚了解概念的含义然后再开始编程。