笔试时间：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 List
from collections import deque

class 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])