数据结构 · 作业题方法复习资料

两个大整数太大无法用普通整型存储，于是把每一位拆成数字存进链表。读入时用头插法逐位插入，输入虽按高位到低位读，链表却变成"个位在前"的顺序；这样从两表头同时往后走就天然对齐数位，模拟手算竖式：本位和 = 两数对应位 + 进位，本位取 sum%10，进位取 sum/10，结果再头插写入新链表，输出即与输入对齐。

while (n1 || n2 || carry) {
    int sum = carry;
    if (n1) { sum += n1->val; n1 = n1->next; }
    if (n2) { sum += n2->val; n2 = n2->next; }
    carry = sum / 10;
    dgi* p = new dgi(sum % 10);
    result->addNode(p);   // 头插，结果低位在前
}

• 时间 O(max(m, n))，m、n 为两数位数
• 空间 O(max(m, n))，新建结果链表所需空间
• 循环条件必须包含 carry，否则 999+1=1000 这类最高位进位会丢失
• 进位与本位顺序不能写反：carry=sum/10、本位=sum%10
• 头插法使链表低位在前，必须理解存储方向，否则会误以为相加错位
• 两链表长度不同时，短链遍历完后指针为空，需用 if(n1)/if(n2) 跳过，禁止解引用空指针
• new 出来的结果节点需交由 intList 析构统一 delete，防止内存泄漏

读入 n 个整数用「带头结点 + 尾指针 tail」建表，每次尾插都是 O(1)，保持输入顺序。逆序时不另开新链：把原首结点 begin 固定为逆序后的尾结点，不断把 begin 后面的结点摘下、用头插法挂到头结点之后，后摘下的排得越靠前，整体顺序就被翻转。每步只动常数个指针，故为就地 O(n)，最后别忘了把 tail 更新为 begin。

void revList() {
    intNode* begin = head->next;
    if (begin == nullptr) return;   // 空表直接返回
    intNode* end = begin->next;
    while (end) {                   // 把end头插到表头之后
        begin->next = end->next;    // 从原位置摘下end
        end->next = head->next;     // end指向当前首结点
        head->next = end;           // end成为新的首结点
        end = begin->next;          // 取begin后的下一个待处理结点
    }
    tail = begin;                   // 原首结点现在是尾结点
}

• 时间 O(n)，每个结点恰好被摘下并头插一次
• 空间 O(1)，只改指针不新建结点
• 逆序后尾结点变为原首结点 begin，忘记更新 tail 会导致后续尾插出错
• 空链表 (begin==nullptr) 需提前 return，否则解引用空指针
• 头插三句赋值顺序不能乱：先 begin->next=end->next 摘除，再 end->next=head->next 接表头，最后 head->next=end
• begin 始终指向原首结点不变，循环靠 end=begin->next 推进；打印时用 first 标志控制空格，避免行末多余空格

对称差集是只在 A 或只在 B、但不同时出现的元素。两表都已按非递减排好，用双指针 i、j 同时从前往后扫描比较 A[i] 与 B[j]：相等是交集，两边等于该值的重复项一并跳过且不入结果；A[i] 小则只在 A，入结果并跳过 A 中相同值；A[i] 大则对称处理 B。某表扫完后，另一表的剩余元素只属于自己，去重后直接加入。一遍线性扫描即可，无需再排序或查找。

while (i < n && j < m) {
    if (A[i] == B[j]) {              // 交集，两边都跳过，不入结果
        int x = A[i];
        while (i < n && A[i] == x) i++;
        while (j < m && B[j] == x) j++;
    } else if (A[i] < B[j]) {        // 只在A中
        int x = A[i]; C[cSize++] = x;
        while (i < n && A[i] == x) i++;
    } else {                         // 只在B中
        int x = B[j]; C[cSize++] = x;
        while (j < m && B[j] == x) j++;
    }
}
// 余下：尾部剩余段各自去重后入C
while (i < n) { int x=A[i]; C[cSize++]=x; while(i<n && A[i]==x) i++; }
while (j < m) { int x=B[j]; C[cSize++]=x; while(j<m && B[j]==x) j++; }

• 时间 O(n + m)，一遍线性扫描
• 空间 O(n + m)，结果数组 C（不计输入）
• 相等时必须同时跳过 A 和 B 中所有等于该值的重复项，否则同一值会被误当成单边元素加入结果
• 去重的内层 while 要先判越界再比较（i<n && A[i]==x），顺序写反会越界
• 输入本身可能含重复元素，单纯逐个比较会漏判，必须成段跳过
• 尾部剩余的两个 while 只会执行其中一个，但仍各自需要去重
• 结果为空要输出 Empty 而不是空行；元素间用 k>0 控制空格分隔

为每个位置 i 求右边第一个严格大于 h[i] 的元素下标（1 基，没有则为 0）。朴素逐个向右扫是 O(n²) 会超时。用单调栈从右往左扫描：栈里存当前位置右侧、从栈顶到栈底高度严格递增的候选下标。处理 i 时先弹掉栈顶所有高度 ≤ h[i] 的元素（它们既不更高又被 h[i] 挡住，对更左的位置也没用），弹完后栈顶即答案，再把 i 压栈供更左侧使用。每个下标至多进出栈各一次，故为线性。

int top = 0;
for (int i = n; i >= 1; i--) {
    while (top > 0 && h[st[top]] <= h[i]) top--; // 弹掉不高于 h[i] 的候选
    ans[i] = (top == 0) ? 0 : st[top];           // 栈顶即右侧第一个更高者下标
    st[++top] = i;                               // 当前下标入栈
}

• 时间 O(n)：每个下标至多进栈出栈各一次，均摊线性
• 空间 O(n)：单调栈 st 与答案数组 ans 各占 O(n)
• 弹栈条件用 h[st[top]] <= h[i]（含等号）才能保证答案是“严格更大”；若要“大于等于”须改为 <
• 下标从 1 开始，ans=0 专表示“右侧不存在更高元素”，真实下标不会为 0
• 数组要开 MAXN=100005 容纳 n 个元素加哨兵余量，越界会出错
• 输出用空格分隔且行尾不留多余空格，靠 i>1 判断控制分隔符
• 从左向右也能做，但栈里存的是“尚未找到答案”的下标，逻辑相反易写错；从右向左更直观

在最近 10 个请求构成的滑动窗口内，对目标 ID 的"被放行"请求做限流。套餐 a/b/c 决定放行上限 limit=3/6/9。用长度 10 的环形数组 q 记录每个槽是否放行了一个目标请求，用计数器 qps 维护窗口内已放行总数。处理第 i 个请求时，先把槽位 pos=i%10（正好是 10 条之前那条记录）从窗口中移除（qps 减旧值并清零），让最早请求滑出，再判断当前请求，从而用 O(1) 空间、O(1) 单步实现定长窗口统计。

int pos = i % 10;          // 该槽位存的是10条之前那个请求
qps -= q[pos];             // 让最早的请求滑出窗口
q[pos] = 0;
if (id != target)      res = 0;          // 非目标，不计数
else if (qps < limit) { res = 1; q[pos] = 1; qps++; }  // 放行
else                   res = -1;         // 达上限，限流

• 时间 O(n)，每个请求 O(1) 处理
• 空间 O(1)（固定长度 10 的数组，与 n 无关）
• 窗口大小固定为 10 要与数组长度 q[10] 一致，pos=i%10 不能写错模数
• 必须先把滑出窗口的旧槽位从 qps 减掉并清零，再处理当前请求，顺序不能颠倒
• 非目标 id 输出 0 且不占名额；被限流的目标输出 -1 也不占名额；只有放行才置 q[pos]=1 并 qps++
• limit 是"窗口内放行上限"而非请求总数限制，判断用 qps<limit（严格小于）
• 输出用空格分隔，第一项前不加空格（i>0 才输出空格）

给定入栈顺序 inSeq 和目标出栈顺序，贪心模拟：依次取出目标里要弹出的 need，只要栈顶不是 need 且入栈序列还有剩余，就不断按序压栈，直到栈顶恰好等于 need 时弹出。若把所有元素都压完仍凑不出 need，则该出栈序列非法。因为出栈序列唯一决定每一步动作，没有别的选择，所以贪心模拟是充要判定。

int top = 0, nextIn = 1; bool ok = true;
for (int i = 1; i <= n; i++) {
    int need; cin >> need;
    if (ok) {
        // 栈顶不是要的数就继续按序压栈
        while ((top == 0 || st[top] != need) && nextIn <= n)
            st[++top] = inSeq[nextIn++];
        if (top > 0 && st[top] == need) top--;   // 匹配则弹出
        else ok = false;                          // 凑不出则非法
    }
}
cout << (ok ? "YES" : "NO") << "\n";

• 时间 O(n)，每个元素至多入栈一次、出栈一次
• 空间 O(n)，存储入栈序列与模拟栈
• while 条件需同时判断 top==0（空栈）与 nextIn<=n（入栈耗尽），否则会访问 st[0] 或越界
• 循环结束后必须再判一次 st[top]==need，因为可能是入栈耗尽而非匹配成功才退出
• 即使已判定 ok=false，仍要继续 cin 读完剩余目标序列，避免输入流错位（用 if(ok) 包裹判断但循环照常读取）
• 出栈序列长度必须与入栈序列长度同为 n

要计算含加减乘除、乘方和括号的整数中缀表达式，直接处理优先级和括号很麻烦。采用经典两步法：先用调度场算法把中缀式转成无括号的后缀式（逆波兰），再用一个操作数栈线性扫描求值。转换时维护一个运算符栈，遇运算符就先把栈顶优先级不低于它的算符弹出输出；关键在用 shouldPop 在优先级相等时靠 cur!='^' 区分，让加减乘除左结合、乘方右结合（2^3^2 按 2^(3^2) 算）。

bool shouldPop(char top, char cur) {
    if (top == '(') return false;           // 左括号在栈内不被普通算符弹出
    if (priority(top) > priority(cur)) return true;
    // 优先级相等时：仅当当前不是 '^' 才弹（左结合弹、右结合不弹）
    return priority(top) == priority(cur) && cur != '^';
}
// 转后缀：遇运算符时
while (!ops.empty() && shouldPop(ops.top(), s[i])) {
    postfix.push_back({false, 0, ops.top()}); ops.pop();
}
ops.push(s[i]);
// 求后缀：b 是右操作数，a 是左操作数
long long b = nums.top(); nums.pop();
long long a = nums.top(); nums.pop();
nums.push(applyOp(a, b, token.op));

• 时间 O(n)，n 为表达式长度；每个字符与每个算符各进出栈一次，幂运算单次为 O(log exp)
• 空间 O(n)，后缀序列与两个栈的空间
• 幂运算右结合，必须在优先级相等时不弹栈（cur=='^' 返回 false），否则 2^3^2 会算成 (2^3)^2=64 而非 512
• 后缀求值时先弹出的是右操作数 b、后弹出的是左操作数 a，顺序写反会让减法和除法出错
• 左括号优先级最低（priority 返回 0），但遇运算符时不能把 '(' 弹出，shouldPop 里需对 top=='(' 特判返回 false
• 遇到 ')' 时要把配对的 '(' 弹出丢弃，不能留在栈里
• 用 long long 防溢出，但未做除零/负指数等非法输入校验，假设输入合法

表面是循环队列模拟（每秒队首买一张，没买完回队尾，直到第 k 人买完）。但总耗时恰等于"第 k 人买完最后一张前所有人累计买到的票数之和"。设 target=tickets[k]：排在 k 前面或本人（i≤k）每轮都先于他买票，最多买 target 张；排在后面的人（i>k）在决定性的最后一轮还没轮到就结束，最多买 target-1 张。各人再与自身票数取 min 后累加，O(n) 直接算出，无需真实维护队列。

int target = tickets[k];
int answer = 0;
for (int i = 0; i < n; ++i) {
    if (i <= k)               // 在 k 前面或就是 k，最多买 target 张
        answer += smaller(tickets[i], target);
    else                      // 在 k 后面，最后一轮没轮到，最多买 target-1 张
        answer += smaller(tickets[i], target - 1);
}
return answer;

• 时间 O(n)（单趟扫描，每人 O(1) 计数）
• 空间 O(n)（仅存票数数组；计数逻辑本身 O(1)）
• i>k 的人上限是 target-1 而非 target——最后一轮还没轮到流程就结束，这是最易错处。
• i==k 归入 i≤k 分支，上限是 target（本人正好买满）。
• i≤k 与 i>k 的分界是初始下标的相对位置，别和动态队列里的实时位置混淆。
• 仍要与 tickets[i] 取 min，否则某人票数本就少于上限时会高估。

反复删除相邻相同字符直到不能再删，会引发连锁删除。用栈一次扫描即可：栈里始终保存"前缀消除后的结果"，新字符只可能与栈顶配对。遍历每个字符 ch，若栈非空且栈顶等于 ch，就弹出栈顶且 ch 也不入栈（成对删掉）；否则把 ch 入栈。最后从栈底到栈顶输出。

for (int i = 0; s[i] != '\0'; ++i) {
    char ch = s[i];
    if (!result.empty() && result.top() == ch) {
        // 栈顶与当前字符相邻相同，成对删除
        result.pop();        // 删栈顶，ch 也不入栈
    } else {
        result.push(ch);     // 不能抵消，暂时保留
    }
}
// 从栈底到栈顶输出即为最终字符串

• 时间 O(n)，每个字符至多入栈一次、出栈一次
• 空间 O(n)，栈最多存放全部字符
• 访问栈顶前必须先确认栈非空，否则空栈 top 会越界读到非法位置
• 配对时是弹出栈顶且当前字符不入栈（一次删两个），别只删一个
• 最终结果可能为空串，需正常输出（空串直接输出换行）
• 输出顺序必须从栈底到栈顶，按出栈顺序会得到反序结果
• char 数组要开到 MAX_LEN+5 留余量，cin>> 读入的串末尾自带 '\0'

一排同速移动的魔像，正数向右、负数向左，只有"左正右负"才会相撞。从左到右扫描，用栈保存当前可能存活的魔像，栈底到栈顶恰好对应长廊从左到右的顺序。正数直接入栈；遇到负数时用 while 不断与栈顶最近的右行魔像比战斗力：栈顶小则弹出继续向左撞，相等则同归于尽，栈顶大则当前被粉碎。循环结束后若当前仍存活就入栈，最终栈中元素即为答案。

bool alive = true;
while (alive && !survivors.empty() && survivors.top() > 0 && cur < 0) {
    long long topPower = absoluteValue(survivors.top());
    long long curPower = absoluteValue(cur);
    if (topPower < curPower)        survivors.pop();          // 栈顶被粉碎，继续向左
    else if (topPower == curPower){ survivors.pop(); alive=false; } // 同归于尽
    else                            alive = false;            // 当前被粉碎
}
if (alive) survivors.push(cur);     // 幸存则入栈

• 时间 O(n)，每个魔像最多入栈一次、出栈一次
• 空间 O(n)，栈最多存放 n 个魔像
• 碰撞判定必须同时满足"栈非空、栈顶为正、当前为负"三条，缺一不可
• 战斗力相等是同归于尽：既要弹栈顶又要置 alive=false 让当前不入栈，两边都不能漏
• 栈顶小被粉碎后当前魔像要继续向左比较下一个栈顶，不能只比一次（用 while 而非 if）
• 正数无论如何直接入栈，不要误判它会和左边碰撞
• 栈空时输出 Empty，不要漏掉空结果的处理；战斗力较大时用 long long 更稳妥

不显式建树，而是把"孩子关系"反向记成父指针数组 parent，使任一结点都能沿 parent 上行到根。先从 x 上行到根，把沿途结点全部标记到 on_path；再让 y 上行，遇到的第一个被标记结点就是两条到根路径的最早交汇点，即最近公共祖先（LCA）。这样把 LCA 转化为"两条到根路径求第一个公共点"，无需求深度、无需递归。

// 1) 孩子关系反存为父指针
for (int i = 1; i <= n; i++) {
    cin >> a >> b;
    if (a) parent[a] = i;   // a 为 0 表示无左孩子
    if (b) parent[b] = i;
}
// 2) 标记 x 到根的整条路径
for (int p = x; p; p = parent[p])
    on_path[p] = true;
// 3) y 向上走，第一个落在 x 路径上的点即 LCA
int ans = y;
while (!on_path[ans]) ans = parent[ans];
cout << ans << endl;

• 时间 O(n)：建父指针 O(n)，两次上行各不超过树高 O(h)≤O(n)
• 空间 O(n)：父指针数组与标记数组各占 n+1
• 读入孩子时若孩子编号为 0 表示空，必须 if(a)/if(b) 判断，否则会误写 parent[0]
• 上行依赖根结点 parent 为 0 才能让 for(p=x;p;...) 自然终止，结点编号需从 1 开始
• x 与 y 之一是另一个的祖先（或 x==y）时仍正确：x 的路径含自身，y 上行会命中
• 假定输入确为一棵合法二叉树，否则上行可能不收敛

把二叉树原地改成一条只沿 right 走的链表，顺序恰为先序（根-左-右），且不用栈或递归只花 O(1) 额外空间。对每个有左子树的结点 cur，找到其左子树的最右结点 pre（左子树先序的最后一个），把 cur 原来的右子树挂到 pre.right，再把整棵左子树搬到 cur 的右边并置空 cur 的左指针，然后沿 right 继续。

while (cur != 0) {
    if (tree[cur].left != 0) {
        int pre = tree[cur].left;
        while (tree[pre].right != 0)   // 找左子树最右结点
            pre = tree[pre].right;
        tree[pre].right = tree[cur].right; // 原右子树挂到前驱后
        tree[cur].right = tree[cur].left;  // 左子树搬到右边
        tree[cur].left  = 0;               // 置空左指针
    }
    cur = tree[cur].right;            // 沿右链前进
}

• 时间 O(n)：每个结点最多被当作前驱查找路径访问常数次，左子树最右链各边总共被走 O(n) 次
• 空间 O(1) 额外空间：除输入存储外仅用常数个指针变量，无栈无递归
• 拼接顺序不能乱：必须先 pre.right=cur.right，再 cur.right=cur.left，最后 cur.left=0，三步顺序错误会丢失子树
• 找前驱 pre 时是沿左子树一路向 right 走到底，不要写成向 left 走
• 下标 0 约定为空，结点从 1 开始存，数组大小要开 n+1
• value 用 long long 防止数值溢出
• 展开后 cur 沿新的 right 前进（此时已是原左子树），而非原来的 right

这是一棵用结构体数组存的完美二叉树（下标1为根，0表空），要给每个节点填 next，指向同层右邻居、最右节点为0。诀窍是不用队列：边走边用「上一层已经连好的 next」去连下一层——同父的左孩子直接连右孩子，右孩子则跨到 cur.next 的左孩子；每层从最左节点 levelStart 横扫，再 levelStart=left 下降一层。每个节点只访问一次，额外空间 O(1)。

int levelStart = root;
while (tree[levelStart].left != 0) {      // 还有下一层
    int cur = levelStart;
    while (cur != 0) {                     // 横向扫当前层
        int l = tree[cur].left, r = tree[cur].right;
        tree[l].next = r;                  // 同父：左->右
        if (tree[cur].next != 0)           // 跨父：右->右邻居的左孩子
            tree[r].next = tree[tree[cur].next].left;
        cur = tree[cur].next;              // 沿上层next横向走
    }
    levelStart = tree[levelStart].left;    // 下降一层
}

例子：完美二叉树 7 个节点，1为根，2/3为第二层，4/5/6/7为叶子层。下图实线为父子边，虚箭头为最终填出的 next 链（同层向右串联）。

• 时间 O(n)，每个节点恰好被处理一次
• 空间 O(1) 额外空间（next 存在节点内，不需要队列；不计输入数组）
• 下标0被用作空节点哨兵，节点编号从1开始，tree 要开 n+1 大小。
• 连右孩子的 next 前必须先判断 cur.next≠0，否则会越界访问 tree[0].left。
• 循环终止条件是 tree[levelStart].left==0（到达叶子层就停），不是 cur==0。
• value 用 long long，防止结点值过大溢出。
• 本题前提是完美二叉树：每个内部节点都有左右孩子，跨父连边的逻辑才成立。

一棵二叉树每个结点存一位数字(0-9)，从根到每个叶子拼成一个数，要把所有这样的数相加。做法是用一次 DFS 枚举所有根到叶路径：进结点压入 path，到叶子就把当前路径数字累加进总和，离开时弹出回溯。由于位数可能很长会溢出整型，总和用 vector 低位在前做高精度加法；为防递归爆栈，用显式栈加 state 标记(0 进入/1 回溯)手工模拟递归的进入与返回两个时机。

if (cur.state == 0) {            // 首次进入该结点
    path.push_back(tree[cur.node].value);
    st.push({cur.node, 1});      // 先压回溯帧，保证孩子处理完再弹path
    if (isLeaf(tree, cur.node)) {
        addPathToSum(path, sum); // 到叶子：把这条路径数字累加进总和
    } else {                     // 先压右后压左 -> 左先出栈(前序)
        if (tree[cur.node].right) st.push({tree[cur.node].right, 0});
        if (tree[cur.node].left)  st.push({tree[cur.node].left, 0});
    }
} else {                         // state==1 回溯
    path.pop_back();
}

例子的树：1 号(值1)有左孩 2 号(值2)、右孩 3 号(值3)，2、3 号都是叶子。

高精度加法(vector 低位在前，下标0是个位)，把 12 与 13 逐位对齐相加：

• 时间 O(总路径数字位数之和)：每个结点遍历一次，每条到叶路径再做一次与当前 sum 等长的高精度加法
• 空间 O(n) 存树、显式栈与 path；总和 vector 占 O(最大位数)
• 回溯帧(state=1)必须先于孩子压栈，否则 path 无法在恰当时机弹出，路径会被污染
• 总和不能用 int 直接累加，位数会溢出，必须用 vector 逐位带进位相加
• addPathToSum 中 path 从高位末尾向个位扫，要与 sum 低位对齐(pos 从0开始)
• 进位 carry 在主循环结束后还要单独 while 处理，否则最高位的进位会丢失
• 用 0 表示空孩子(left==0/right==0 判叶)，结点下标从1开始，tree 数组开到 n+1
• 输出前去前导0要保留至少一位(size>1 才弹0)，避免和为0时输出空

用一次非递归先序遍历同时完成遍历与改链：手写顺序栈代替递归（n 可达 10 万，退化成链时递归会爆栈），处理当前结点 cur 时先压右孩子再压左孩子保证下轮先弹左，符合"根左右"。改链用 prev 记录先序中上一个结点，每访问 cur 就令 prev.left=0、prev.right=cur，逐步串成只走 right 的单链表。

nodes.push(root);
int prev = 0;
while (!nodes.empty()) {
    int cur = nodes.pop();
    int L = tree[cur].left, R = tree[cur].right; // 先暂存原孩子
    if (prev != 0) { tree[prev].left = 0; tree[prev].right = cur; }
    if (R != 0) nodes.push(R);   // 先压右
    if (L != 0) nodes.push(L);   // 再压左，下一轮先弹左
    prev = cur;
}
if (prev != 0) { tree[prev].left = 0; tree[prev].right = 0; } // 收尾

例子：根 1，左孩子 2、右孩子 3（均为叶子，靠入度为 0 找到根 1）。

• 时间 O(n)，每个结点恰好入栈出栈一次
• 空间 O(n)，结构体数组与显式栈，最坏栈深 O(n)
• 改链前必须先暂存 originalLeft/originalRight，否则覆盖 right 后再压栈会丢子树
• 压栈顺序必须"先右后左"，反了会变成根右左
• 循环结束后还要把最后一个结点 prev 的 left 和 right 都置 0，否则末尾残留旧指针
• 根结点不在输入给出，须靠 hasParent 找入度为 0 的点，不能想当然认为是 1 号
• 结点值范围 -1e9~1e9，用 long long 更稳妥；递归实现在退化成链(深度 10 万)时会运行时栈溢出

这是一棵满二叉树（完美二叉树），可以省掉层序队列：同一父节点必有 left.next = right；若父节点在本层还有右邻居（cur.next≠0），则 right.next = cur.next.left。所以只要上一层的 next 已建好，就能沿这一层的 next 横向移动，顺手把下一层全部连好。逐层从根往下，levelStart 记录每层最左节点作横向起点，额外空间仅 O(1)。

void connectNextPointers(int root) {
    tree[root].next = 0;
    int levelStart = root;
    while (tree[levelStart].left != 0) {     // 还有下一层
        int cur = levelStart;
        while (cur != 0) {                   // 沿本层 next 横向走
            tree[tree[cur].left].next = tree[cur].right;        // 同父：left->right
            if (tree[cur].next != 0)
                tree[tree[cur].right].next = tree[tree[cur].next].left; // 跨父：right->nextLeft
            else
                tree[tree[cur].right].next = 0;                 // 本层最右
            cur = tree[cur].next;
        }
        levelStart = tree[levelStart].left;  // 下一层最左节点
    }
}

• 时间 O(n)，每个节点恰好被访问并连接一次
• 空间 O(n) 存树本身；额外辅助空间仅 O(1)，不用队列/递归栈
• 仅对满二叉树成立：right.next=next.left 依赖每个父节点都有两个孩子，普通二叉树需改用队列层序
• 终止条件用 tree[levelStart].left!=0 判断是否到叶子层，而非靠层数计数
• 本层最右父节点 cur.next==0，必须显式把它的 right.next 置 0
• 输出按编号 1..n 顺序（第 i 行输出节点 i 的 next），不是按层序或先序
• 0 既表示空孩子也表示空 next，需统一约定；节点值范围 [-1e9,1e9] 用 long long 读入保结构

每条根到叶的路径把沿途结点数字依次拼成一个十进制整数，求所有这些数之和。因为 n 可达 10 万且树可能退化成长链，递归 DFS 会爆栈，所以用手写顺序栈做非递归 DFS，栈元素携带结点编号和深度，深度用来定位该数字在路径数组中的位置。又因单条路径可长达 10 万位，远超 long long，所以用 int 数组逆序保存大整数（下标 0 是个位），每到叶子就按竖式逐位带进位累加。根是唯一没有父亲的结点（入度为 0）。

void calculateSum(int root) {
    ItemStack nodes;
    nodes.push({root, 1});
    while (!nodes.empty()) {
        StackItem cur = nodes.pop();
        int node = cur.node, depth = cur.depth;
        pathDigits[depth] = tree[node].value;     // 按深度记录路径上的数字
        if (isLeaf(node)) {
            addCurrentPathToSum(depth);           // 到叶子: 把整条路径数字累加进大整数
        } else {                                  // 先压右再压左, 左子树先出栈
            if (tree[node].right) nodes.push({tree[node].right, depth + 1});
            if (tree[node].left)  nodes.push({tree[node].left,  depth + 1});
        }
    }
}

• 时间 O(n + S), S 为所有叶子路径长度之和(每到叶子做一次与路径等长的大整数加法); 退化成链时最坏可达 O(n²) 量级
• 空间 O(n), 结点表、手写栈、路径数组、大整数数组均为 O(n) 级别
• 路径可长达 10 万位, 必须用大整数逆序数组, 绝不能用 long long
• 树退化成链时递归会栈溢出, 必须用手写栈做非递归 DFS
• 大整数累加要带进位, 进位可能使位数增长, 需同步更新 sumLength
• 大整数是逆序存的, 输出要从高位到个位并去掉前导 0
• 答案为 0 时应输出单个 0 而非空行
• left/right 为 0 表示空孩子, 叶子判定是左右孩子都为 0; pathDigits 只用 1..depth 这一段, 更深层旧值不影响结果, 无需清理

题目要支持「插入一个数」和「取出当前最小数」，最适合用小根堆。用 vector 把完全二叉树按层存进数组，下标 0 占位、从 1 开始，于是节点 i 的父亲是 i/2、左右孩子是 2i、2i+1。插入时把新值放数组末尾再上浮(siftUp)，取最小时输出堆顶 heap[1]、把末尾搬上来再下沉(siftDown)，每次操作均 O(log n)。

void siftUp(int i){              // 上浮：比父亲小就换上去
    while(i>1 && heap[i]<heap[i/2]){
        swap(heap[i], heap[i/2]); i/=2;
    }
}
void siftDown(int i){           // 下沉：与较小孩子比较
    int sz=heap.size()-1;
    while(i*2<=sz){
        int c=i*2;
        if(c+1<=sz && heap[c+1]<heap[c]) c++;   // 选较小孩子
        if(heap[i]<=heap[c]) break;
        swap(heap[i],heap[c]); i=c;
    }
}
// 删除堆顶：输出heap[1]，把末尾搬到堆顶后下沉
heap[1]=heap.back(); heap.pop_back(); siftDown(1);

• 时间 每次插入/删除 O(log n)，n 个操作共 O(n log n)
• 空间 O(n)，仅存堆数组
• 小根堆下沉要和「较小的」孩子比较交换，写成较大孩子会错
• siftUp 循环条件必须 i>1，到根(下标1)即停，否则 i/2 会越界访问占位元素 heap[0]
• siftDown 中右孩子可能不存在，必须先判 c+1<=sz 再访问 heap[c+1]
• 相等时(<=)应停止，避免无谓交换甚至死循环
• 删除堆顶要先把末尾值赋给 heap[1] 再 pop_back，顺序写反会丢数据
• 数组有效大小是 heap.size()-1（因下标0占位），算 sz 别忘了减 1

WPL（带权路径长度）等于所有叶子结点的权值乘以其深度之和。用结构体数组静态存树（孩子用编号表示，0 代表空），通过 hasParent 标记找出唯一没有父亲的结点作为根；再用两个并行的栈同步保存「结点编号」与「对应深度」，做非递归 DFS：弹出叶子就累加 weight×depth，否则把孩子压栈并令深度加一。用迭代代替递归是为了树很深时避免系统栈溢出。

while (!stackNode.empty()) {
    int node = stackNode.back();  stackNode.pop_back();
    int depth = stackDepth.back(); stackDepth.pop_back();
    if (isLeaf(tree[node])) {
        wpl += tree[node].weight * depth;      // 叶子: 权值×深度
    } else {
        if (tree[node].right) { stackNode.push_back(tree[node].right);
                                stackDepth.push_back(depth + 1); }
        if (tree[node].left)  { stackNode.push_back(tree[node].left);
                                stackDepth.push_back(depth + 1); }
    }
}

• 时间 O(n)，每个结点恰好入栈出栈一次
• 空间 O(n)，结构体数组与栈深度最坏为 O(n)
• 根不一定是 1 号结点，必须靠「无父结点」(hasParent) 确定，否则 WPL 算错
• 深度从 0 开始：根深度为 0，且非叶根的权值不计入 WPL
• 只对叶子（左右孩子编号都为 0）累加权值，内部结点的 weight 不计入
• 孩子编号为 0 表示空指针，判叶子与压栈前都要判 0
• wpl 与 weight 都要用 long long，权值累加很大时防止 int 溢出

先把 n 个数依次插入一棵二叉排序树(BST)：每个数从根出发，比当前结点小就向左、否则向右，遇到空孩子就挂上去。再查找关键字 k，按同样的下行规则从根走到 k，沿途记录经过的结点值即为查找路径；若走到空(-1)说明查找失败，在路径末尾补一个 -1。

// 插入：小于向左，否则向右，遇空位即挂上
while (true) {
    if (x < tree[current].value) {
        if (tree[current].left == -1) {
            tree[current].left = tree.size();   // 先记下孩子下标
            tree.push_back(Node(x));            // 再插入新结点
            return;
        }
        current = tree[current].left;
    } else {
        if (tree[current].right == -1) {
            tree[current].right = tree.size();
            tree.push_back(Node(x));
            return;
        }
        current = tree[current].right;
    }
}

// 查找：沿途记录路径，命中即停，走到空补 -1
while (current != -1) {
    path.push_back(tree[current].value);
    if (target == tree[current].value) return path;
    current = (target < tree[current].value) ? tree[current].left
                                             : tree[current].right;
}
path.push_back(-1);

• 时间 建树 O(n·h)，单次查找 O(h)，h 为树高（最坏 O(n)，平衡时 O(log n)）
• 空间 O(n)，存储 n 个结点
• 相等元素的归属：代码用 x < value 才向左，等于时归入右子树（右边为 ≥），需与题意一致
• 插入空树要单独判断 tree.empty()，否则访问 tree[0] 越界
• 孩子下标必须在 push_back 之前用 tree.size() 取，push_back 之后 size 已改变
• 查找失败时别忘了输出 -1，且 -1 也要参与空格分隔的格式
• 根结点固定为下标 0，整个算法依赖第一个插入的数当根

给两张同样大小的 0/1 网格 grid1、grid2，上下左右相连的 1 算一个岛屿。遍历 grid2，遇到未访问的 1 就用栈做一次 DFS 把整片连通块走完；过程中只要某格在 grid1 里是 0 就给岛屿打标记 ok=false（只标记、不提前退出），走完整块后若 ok 仍为真则计数加一。把访问过的格子直接写回 grid2 置 0，既当 visited 又防重复统计。

if (grid2[i][j] == 0) continue;
bool ok = true;
stack<pair<int,int>> st;
st.push({i, j}); grid2[i][j] = 0;     // 标记起点
while (!st.empty()) {
    auto [x, y] = st.top(); st.pop();
    if (grid1[x][y] == 0) ok = false; // 只标记，不提前退出
    for (int k = 0; k < 4; ++k) {
        int nx = x+dx[k], ny = y+dy[k];
        if (nx<0||nx>=m||ny<0||ny>=n) continue;
        if (grid2[nx][ny] == 1) {      // 先标记后入栈
            grid2[nx][ny] = 0;
            st.push({nx, ny});
        }
    }
}
if (ok) ++ans;

• 时间 O(m*n)，每个格子至多入栈、出栈一次
• 空间 O(m*n)，最坏栈中存放整片连通区域；直接复用 grid2 当 visited，无额外标记数组
• 不能一遇到 grid1[x][y]==0 就 break：必须先把整个岛屿所有格子标记完，否则剩余格子会被外层循环当成新岛屿重复统计
• 判定标记 ok 只能置为 false，不要在循环里又把它重新置回 true
• 先 grid2[nx][ny]=0 再 push（先标记后入栈），否则同一格可能被重复压栈处理；起点 (i,j) push 后也要立即置 0
• 访问网格前先做 nx/ny 越界判断，避免下标越界

求弱连通分量就是忽略边的方向后，两点是否在同一无向连通块里，本质等价于求无向图的连通分量个数。因此不必真正建图，读入每条有向边 u→v 就把 u、v 两个集合合并；处理完所有边后，统计根节点（findRoot(i)==i）的个数即为答案。自环和重边因合并同根会直接返回，不影响结果。

int findRoot(int x) {            // 路径压缩，纯循环
    int root = x;
    while (parent[root] != root) root = parent[root];
    while (parent[x] != x) { int p = parent[x]; parent[x] = root; x = p; }
    return root;
}
void unite(int a, int b) {       // 按集合大小合并
    int ra = findRoot(a), rb = findRoot(b);
    if (ra == rb) return;        // 同集合（重边/已连通）直接返回
    if (setSize[ra] < setSize[rb]) swap(ra, rb);  // 小挂大
    parent[rb] = ra; setSize[ra] += setSize[rb];
}
// 主流程：每条边 if(u!=v) unite(u,v); 最后统计 findRoot(i)==i 的个数

• 时间 O((n+m)·α(n))，近似 O(n+m)
• 空间 O(n)（只用 parent 与 setSize 两个数组）
• 弱连通≠强连通：本题忽略方向，不要去做 Tarjan/Kosaraju 求强连通
• 节点编号从 1 开始，初始化与统计都用 1..n，别写成 0..n-1
• 自环 u→u 不改变连通性应跳过（即使不跳，unite 同根也会直接 return）
• 统计集合数要用 findRoot(i)==i 判断根，而非直接看 parent[i]==i（未压缩时可能漏判）
• 按大小合并时务必把 setSize 累加到新根上，否则后续合并失衡

无权图里每条边长度都看作 1，求 s 到 t 的最短路就是求最少边数。BFS 从起点一层层向外扩展：第 0 层是 s，第 1 层是它的直接邻居……由于按距离从小到大发现节点，某点第一次被访问时一定走的是最少边数，所以第一次碰到 t 得到的 distance 就是答案。用 distance[i]=-1 既表示未访问又当 visited 标记，自环和重边都自动失效。

distance[s] = 0;
nodes.push(s);
while (!nodes.empty()) {
    int current = nodes.pop();
    for (int e = graph.firstEdge(current); e != 0; e = graph.nextOf(e)) {
        int nb = graph.targetOf(e);
        if (distance[nb] != -1) continue;          // 已访问跳过(去重/防环)
        distance[nb] = distance[current] + 1;       // 层数+1
        if (nb == t) return distance[nb];           // 第一次到t即最短
        nodes.push(nb);
    }
}
return -1;                                          // s与t不连通

• 时间 O(n+m)：每个点最多入队一次，每条边只遍历一次
• 空间 O(n+m)：邻接表存 2m 条有向边，队列与 distance 各 O(n)
• s==t 必须特判返回 0，否则起点被标记后会漏判而返回 -1。
• distance 初始化为 -1 而非 0，否则无法区分起点（距离 0）和未访问点。
• 链式前向星边号从 1 开始，head[u]==0 表示空表，0 不能当真实边号。
• 找到 t 应在标记 distance 后立即 return，不要等出队再判断。
• 无向边要正反各存一条，邻接表数组须开 2*m；读入时 u==v 显式忽略自环。

给定有向图，判断从起点 s 能否到达终点 t。从 s 出发做一次 BFS 遍历，凡能被遍历到的点都是 s 可达的，所以只要遍历途中碰到 t 就说明可达。用队列保存待扩展节点，用 visited 数组防止重复入队，出队时若节点等于 t 立刻输出 True，队列空了仍没遇到则输出 False。只判可达性，BFS/DFS 皆可。

visited[s] = true;
q.push(s);
while (!q.empty()) {
    int u = q.front(); q.pop();
    if (u == t) { cout << "True\n"; return 0; }
    for (int v : graph[u])
        if (!visited[v]) {
            visited[v] = true;   // 入队即标记
            q.push(v);
        }
}
cout << "False\n";

• 时间 O(n + m)，每个节点最多入队一次，每条边最多被检查一次
• 空间 O(n + m)，邻接表存边 O(n+m)，visited 与队列 O(n)
• 有向图只能 graph[u].push_back(v) 加单向边，不可当无向图加双向
• visited 要在入队时立刻置真，而非出队时，否则同一点可能被多次压入队列
• 顶点编号从1开始，容器大小要开 n+1 防越界
• 需处理 s==t：s 先入队，出队时判 u==t 即可正确返回 True
• 输出大小写与换行要严格匹配 True/False

网格中每走一步代价都是 1，这是无权图上的单源最短路，最适合用 BFS。从 S 出发按层一圈圈向外扩展，队列保证先访问的格子距离一定不更大，所以第一次到达 A 时的 dist 就是最少步数。用 dist 数组兼作访问标记（-1 表示未访问），入队即赋距离并标记，走不到就输出 -1。

dist[sx][sy] = 0; q.push({sx, sy});
int dx[4]={1,-1,0,0}, dy[4]={0,0,1,-1};
while (!q.empty()) {
    auto [x, y] = q.front(); q.pop();
    if (grid[x][y] == 'A') { cout << dist[x][y]; return 0; }
    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 (grid[nx][ny]=='#' || dist[nx][ny]!=-1) continue;
        dist[nx][ny] = dist[x][y] + 1;   // 入队即赋距离并标记
        q.push({nx, ny});
    }
}
cout << -1;  // 走不到

• 时间 O(n·m)，每个格子最多入队、出队各一次，每次扩展常数个方向
• 空间 O(n·m)，dist 数组与队列规模均与格子数同阶
• 必须在入队时就赋 dist 标记已访问，而不是出队时才标记，否则同一格会被多次入队导致超时
• 起点 S 也要先 dist=0 并入队，否则会从 S 重复出发
• 边界（越界）检查要在访问 grid[nx][ny] 之前完成，避免数组越界
• 障碍 # 与已访问格子（dist≠-1）都要跳过
• 无法到达 A 时循环结束后别漏掉输出 -1

数组 scores 已按非递减顺序存储，要找第一个不小于目标值 x 的下标。每次询问若线性扫描是 O(n)，q 次会超时；利用有序性改用二分查找把单次降到 O(log n)。二分时用变量 answer 记录候选：mid 处值 ≥ target 就先记下并向左收缩找更靠前的位置，否则到右半部分继续。

int left = 1, right = scores.size() - 1, answer = 0;
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (scores[mid] >= target) {   // mid 可能是答案
        answer = mid;
        right = mid - 1;           // 继续向左找更靠前的
    } else {
        left = mid + 1;            // 答案在右半部分
    }
}
return answer;

• 时间 每次询问 O(log n)，总体 O((n+q) + q·log n)
• 空间 O(n) 存数组，二分本身 O(1)
• 数组必须有序二分才成立；answer 初值 0 表示没有元素 ≥ target（x 比所有元素都大）
• 比较用 >= 而非 >，否则找到的是第一个严格大于 target 的位置（变成 upper_bound）
• 循环条件 left <= right 配合 right=mid-1，写成开区间易死循环或漏判
• 下标从 1 开始，right 初始化为 size()-1；mid = left+(right-left)/2 防溢出

两个分别升序的数组 a、b，求合并后第 k 小元素。利用有序性，每轮比较两侧各自第 half=k/2 个元素，较小一侧的前 half 个必定排在第 k 名之前，整体丢弃并把 k 减去丢弃数量，从而每轮把 k 大约减半，O(log k) 轮即可定位答案，无需真正归并。

int half = remain / 2;
int checkA = min(startA + half - 1, n);   // 越界夹到末尾
int checkB = min(startB + half - 1, m);
if (a[checkA] <= b[checkB]) {             // a 侧前缀更小，整体淘汰
    remain -= (checkA - startA + 1);
    startA = checkA + 1;
} else {                                   // b 侧前缀更小，整体淘汰
    remain -= (checkB - startB + 1);
    startB = checkB + 1;
}
// 出口：某侧空 -> 另一侧取第 remain 个；remain==1 -> 取两队首较小者

• 时间 单次询问 O(log(k)) ≈ O(log(n+m))，q 次共 O(q·log(n+m))；建表 O(n+m)
• 空间 O(n+m) 存数组，查询本身仅 O(1) 额外空间（迭代无递归栈）
• 比较的是各侧第 half 个元素 a[startA+half-1]，不是中点；下标 -1 不能漏
• checkA/checkB 可能越界，必须夹到 n/m，否则数组越界访问
• 淘汰数量 removed=checkA-startA+1（含端点），k 要减真实数量而非固定 half
• remain==1 的出口必须有，否则 half=0 永远排不动会死循环
• 某数组已空（startA>n）时直接去另一侧取第 remain 个，下标是 startB+remain-1

把每个数替换成它在所有不同取值里由小到大的名次。做法是离散化：复制全部数后排序，用 unique 去重得到严格递增的 values，再对每个原始元素用 lower_bound 二分找到它第一次出现的位置，下标加一即排名。相同的值得到相同名次。

用二分而非逐个扫描，是因为 values 已有序，单次查询从 O(m) 降到 O(log m)，把可能很大的数值压缩到 1..m 的连续小整数。

sort(values.begin(), values.end());
values.erase(unique(values.begin(), values.end()), values.end());

for (int i = 0; i < n; ++i) {
    int rank = lower_bound(values.begin(), values.end(), a[i])
               - values.begin() + 1;
    cout << rank;
    if (i + 1 < n) cout << ' ';
}

• 时间 O(n log n)，排序与 n 次二分查找均为对数级
• 空间 O(n)，需保存原数组与去重后的有序数组
• 排名从 1 开始计数，lower_bound 减 begin 得到的是 0-based 下标，必须 +1，漏掉会全部少 1
• 必须先 sort 再 unique，unique 只能去除相邻重复，未排序会去重失败
• unique 不会真正缩短容器，要配合 erase 删掉尾部残留元素
• 相同值应得相同名次，要用 lower_bound（第一个不小于的位置），不能误用 upper_bound
• 输出时用 i+1<n 判断边界，末尾不要多打空格

把每个学生封装成结构体，读入时就预先算好总分 sum=a+b，避免在比较时反复相加。排序用多关键字字典序：先按总分降序，总分相同看第二门成绩 b 降序，仍相同则按学号 id 升序，保证结果唯一可复现。

sort(students.begin(), students.end(),
     [](const Student& x, const Student& y) {
    if (x.sum != y.sum) return x.sum > y.sum; // 总分降序
    if (x.b   != y.b)   return x.b   > y.b;   // 次门成绩降序
    return x.id < y.id;                       // 学号升序
});

• 时间 O(n log n)，std::sort 主导
• 空间 O(n)，存放结构体数组
• 比较器必须满足严格弱序：相等时返回 false，用 != 逐级判断才安全，否则 sort 可能崩溃
• 主键 sum 与次键 b 都是降序(>)，但学号 id 是升序(<)，方向不要写反
• 总分相同时若漏掉 id 这一级，输出顺序可能不确定
• 应预存 sum，比较里直接写 x.a+x.b 会重复计算且易写错