✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线200+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

联想-2026.03.19

题目一：二叉树重建与前序遍历

1️⃣：先把每个节点的左右孩子关系存下来

2️⃣：统计哪些字符曾作为孩子出现，从而反推出根节点

3️⃣：从根节点出发做一次前序遍历，依次输出访问顺序

难度：中等

这道题本质上是模拟建树。输入规模不大，但需要先想清楚“根节点是谁”这个关键点：根一定是那个从未作为别人孩子出现过的节点。找到根以后，前序遍历就是标准树遍历了。

题目二：数组分块求最小最大值

1️⃣：把问题改写成在前缀和上选择两刀

2️⃣：固定第一刀后，第二刀只需要在“平衡后两段”的附近检查

3️⃣：利用单调性让第二刀指针整体只向右移动一次

难度：中等

这道题表面像二分答案，其实还可以继续压到线性。由于数组元素全为正数，前缀和严格递增，第二刀的最优位置会随着第一刀单调右移，因此双指针扫一遍就能得到最优解。

01. 二叉树重建与前序遍历

问题描述

小基 在整理一批古文明留下来的“记忆碎片”。研究人员确认，这些碎片共同描述了一棵二叉树：每一条记录都会给出某个节点，以及它的左孩子和右孩子。

现在需要你根据这些记录，把整棵二叉树重新建出来，并输出这棵树的前序遍历结果。

输入中的每一行由三个字符组成，依次表示：

• 当前节点
• 左孩子
• 右孩子

其中字符 * 表示该位置没有孩子。

输入格式

第一行输入一个整数 ，表示二叉树中的节点个数。

接下来 行，每行包含一个长度为 的字符串，表示一条节点记录。

输出格式

输出一个字符串，表示这棵二叉树的前序遍历序列。

样例输入

3
rxb
x**
b**

样例输出

rxb

数据范围

• 
• 所有节点字符互不相同
• 输入保证这些记录能够唯一确定一棵合法的二叉树

题解

这道题分成两步：

1. 先建树。
2. 再做前序遍历。

第一步：把每个节点的左右孩子存下来

每条记录都是三个字符：

• 第一个字符是当前节点
• 第二个字符是左孩子
• 第三个字符是右孩子

所以我们可以用一个映射表直接记录：

• left[u]
• right[u]

同时，凡是出现在“孩子位置”的字符，都标记为“它不是根”。

第二步：找到根节点

二叉树里除了根节点以外，其他所有节点都会作为某个节点的左孩子或右孩子出现一次。

因此：

• 出现在节点集合里
• 但从来没有作为孩子出现过

的那个字符，就是整棵树的根。

第三步：从根开始做前序遍历

前序遍历顺序是：

1. 访问当前节点
2. 遍历左子树
3. 遍历右子树

直接递归即可。

为什么这样一定正确

输入已经给出了每个节点的左右孩子，因此整棵树的结构信息是完整的。

而根节点的判定也很直接：

• 非根节点一定会作为别人孩子出现
• 根节点不会作为任何人的孩子出现

所以找到根以后，再按照前序遍历定义递归访问，就能得到唯一正确的答案。

复杂度分析

设节点数为 。

• 建树复杂度：
• 找根复杂度：
• 前序遍历复杂度：

总时间复杂度为 ，空间复杂度为 。

参考代码

• Python

import sys

input = lambda: sys.stdin.readline().strip()


def solve() -> None:
    n = int(input())
    children = {}
    nodes = []
    is_child = set()

    for _ in range(n):
        s = input()
        u, lch, rch = s[0], s[1], s[2]
        children[u] = (lch, rch)
        nodes.append(u)
        if lch != "*":
            is_child.add(lch)
        if rch != "*":
            is_child.add(rch)

    root = ""
    for u in nodes:
        if u not in is_child:
            root = u
            break

    ans = []

    def preorder(u: str) -> None:
        if u == "*":
            return
        ans.append(u)
        lch, rch = children[u]
        preorder(lch)
        preorder(rch)

    preorder(root)
    sys.stdout.write("".join(ans))


if __name__ == "__main__":
    solve()

• Cpp

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

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

    int n;
    cin >> n;

    vector<char> nodes;
    array<pair<char, char>, 256> children;
    array<bool, 256> is_child{};

    for (int i = 0; i < 256; ++i) {
        children[i] = {'*', '*'};
    }

    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        char u = s[0], lch = s[1], rch = s[2];
        nodes.push_back(u);
        children[(unsigned char)u] = {lch, rch};
        if (lch != '*') {
            is_child[(unsigned char)lch] = true;
        }
        if (rch != '*') {
            is_child[(unsigned char)rch] = true;
        }
    }

    char root = '*';
    for (char u : nodes) {
        if (!is_child[(unsigned char)u]) {
            root = u;
            break;
        }
    }

    string ans;
    function<void(char)> preorder = [&](char u) {
        if (u == '*') {
            return;
        }
        ans.push_back(u);
        auto [lch, rch] = children[(unsigned char)u];
        preorder(lch);
        preorder(rch);
    };

    preorder(root);
    cout << ans;
    return 0;
}

• Java

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());

        char[][] children = new char[256][2];
        boolean[] isChild = new boolean[256];
        char[] nodes = new char[n];

        for (int i = 0; i < 256; i++) {
            children[i][0] = '*';
            children[i][1] = '*';
        }

        for (int i = 0; i < n; i++) {
            String s = br.readLine().t