笔试时间：2024年04月01日   历史笔试传送门：2023秋招笔试合集  第一题  题目：二叉树的层序遍历  给定数值无重复的二叉树的前序和中序遍历结果数组，输出此二叉树的层序遍历结果的数组。  样例输入     [1,2,3,4,5],[2,1,4,3,5]    样例输出     [1,2,3,4,5]    参考题解  前序遍历的第一个数字是根节点，找到它在中序遍历结果的索引，根据索引分成左右两个子树，之后递归即可。最后，再层序遍历返回数组。  C++：[此代码未进行大量数据的测试，仅供参考]  class Solution {public:    /**     * Note: 类名、方法名、参数名已经指定，请勿修改     *     *      * 层序打印二叉树     * @param pre int整型 vector 前序遍历数组     * @param mid int整型 vector 中序遍历数组     * @return int整型vector     */    struct Node {        int val;        Node* left, *right;        Node(int x = 0, Node* l = nullptr, Node* r = nullptr) {            val = x, left = l, right = r;        }    };    vector<int> levelPrintTree(vector<int>& pre, vector<int>& mid) {        int n = pre.size();        Node* root = helper(pre, 0, n - 1, mid, 0, n - 1);        vector<int> ans;        if (!root) return ans;        queue<Node*> q;        q.push(root);        while (!q.empty()) {            int sz = q.size();            while (sz--) {                root = q.front(); q.pop();                ans.push_back(root->val);                if (root->left) q.push(root->left);                if (root->right) q.push(root->right);            }        }        return ans;    }    Node* helper(vector<int>& pre, int s1, int e1, vector<int>& mid, int s2, int e2) {        if (s1 > e1) return nullptr;        if (s1 == e1) return new Node(pre[s1]);        Node* root = new Node(pre[s1]);        int pos2 = 0;        for (int i = s2; i <= e2; ++i) if (mid[i] == pre[s1]) { pos2 = i; break; }        int pos1 = s1 + pos2 - s2;        root->left = helper(pre, s1 + 1, pos1, mid, s2, pos2 - 1);        root->right = helper(pre, pos1 + 1, e1, mid, pos2 + 1, e2);        return root;    }};  Java：[此代码未进行大量数据的测试，仅供参考]  import java.util.*;class Solution {    public static class Node {        int val;        Node left, right;        Node(int x) {            val = x;            left = null;            right = null;        }    }    public List<Integer> levelPrintTree(List<Integer> pre, List<Integer> mid) {        int n = pre.size();        Node root = helper(pre, 0, n - 1, mid, 0, n - 1);        List<Integer> ans = new ArrayList<>();        if (root == null) return ans;        Queue<Node> q = new LinkedList<>();        q.add(root);        while (!q.isEmpty()) {            int sz = q.size();            while (sz-- > 0) {                root = q.poll();                ans.add(root.val);                if (root.left != null) q.add(root.left);                if (root.right != null) q.add(root.right);            }        }        return ans;    }    private Node helper(List<Integer> pre, int s1, int e1, List<Integer> mid, int s2, int e2) {        if (s1 > e1) return null;        if (s1 == e1) return new Node(pre.get(s1));        Node root = new Node(pre.get(s1));        int pos2 = 0;        for (int i = s2; i <= e2; ++i) {            if (mid.get(i) == pre.get(s1)) {                pos2 = i;                break;            }        }        int pos1 = s1 + pos2 - s2;        root.left = helper(pre, s1 + 1, pos1, mid, s2, pos2 - 1);        root.right = helper(pre, pos1 + 1, e1, mid, pos2 + 1, e2);        return root;    }}  Python：[此代码未进行大量数据的测试，仅供参考]  from typing import Listfrom collections import dequeclass Solution:    class Node:        def __init__(self, x=0, left=None, right=None):            self.val = x            self.left = left            self.right = right    def levelPrintTree(self, pre: List[int], mid: List[int]) -> List[int]:        def helper(pre, s1, e1, mid, s2, e2):            if s1 > e1:                return None            if s1 == e1:                return self.Node(pre[s1])