虾皮笔试 虾皮笔试题 0401
笔试时间: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])
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
2024 BAT笔试合集 文章被收录于专栏
持续收录字节、腾讯、阿里、美团、美团、拼多多、华为等笔试题解,包含python、C++、Java多种语言版本,持续更新中。