美团 · 树 · 算法编程题
美团 树 N ≤ 300 时限 1 秒 / 256 MB

题目描述

小团有一个由N个节点组成的二叉树，每个节点有一个权值。定义二叉树每条边的开销为其两端节点权值的乘积，二叉树的总开销即每条边的开销之和。小团按照二叉树的中序遍历依次记录下每个节点的权值，即他记录下了N个数，第i个数表示位于中序遍历第i个位置的节点的权值。之后由于某种原因，小团遗忘了二叉树的具体结构。在所有可能的二叉树中，总开销最小的二叉树被称为最优二叉树。现在，小团请小美求出最优二叉树的总开销。

输入输出

输入描述
第一行输入一个整数N（1<=N<=300），表示二叉树的节点数。
第二行输入N个由空格隔开的整数，表示按中序遍历记录下的各个节点的权值，所有权值均为不超过1000的正整数。
输出描述
输出一个整数，表示最优二叉树的总开销。

样例共 1 组

样例 1 · 最优二叉树如图所示，总开销为7*1+6*5+5*1+1*3=45。
输入
5
7 6 5 1 3
输出
45

算法解析依据一般

考点：树

数据规模 N ≤ 300 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：N ≤ 300
  • 复杂度门槛：允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

参考方向：树

树结构上的遍历（DFS 求子树信息 / BFS 求层序），多数树题是「后序遍历 + 回溯」。

思路框架（树 通法 · 非本题专属）

  1. 按输入建图（父子关系一般给父节点编号，孩子用邻接表存）。
  2. 确定遍历方式：自底向上合并子树信息（后序 DFS）或自顶向下传参（前序 DFS）。
  3. 对每个节点，用孩子的答案合并出当前节点的答案。
  4. 涉及层间操作（如层序变换）时用 BFS 逐层处理。

实现要点：递归深度可能到 1e5，注意递归爆栈；必要时改迭代或调整递归深度。

复杂度：时间 O(n) ｜ 空间 O(n)

该范式的通法易错点

  • 递归深度过大导致爆栈。
  • 建树时父子关系方向搞反（把树当成有向图但遍历方向错）。

对照本题

  • 数据规模 N ≤ 300，允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。

样例解读

样例 1：输入 5 / 7 6 5 1 3 → 输出 45

最优二叉树如图所示，总开销为7*1+6*5+5*1+1*3=45。

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：美团2023校招笔试第10场编程题。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解