华为 · 树 · 算法编程题
华为 树 时限 1 秒 / 256 MB

题目描述

·
决策树若完全按训练集递归生长，往往能把训练样本分得很“细”，但一到未见过的数据就容易出错，即出现过拟合。为缓解这一问题，常用“剪枝”把某些子树整体替换成单个叶子，使模型更简单。
·
现在有一棵用于二分类的二叉决策树（标签1表示正类，0表示负类）。对非叶节点，按“第 f_i 个特征 ≤ th_i 走左子树，否则走右子树”的规则继续判断；到达叶子时直接输出该节点自带的 label 。
·
允许在整棵树上任选若干处进行剪枝（把某个内部节点整体替换为叶节点，其输出为该节点给定的 label ）。请在给定验证集上寻找使 F1 值最大的剪枝方案，输出最优 F1（四舍五入保留6位小数）。

输入输出

输入描述
第一行：N M K
N 为节点数(1~100)，M 为验证集条数(1~300)，K 为每条验证样本的特征维数(1~100)。
接下来的 N 行：按节点编号1..N给出每个节点的信息：
l_i r_i f_i th_i label_i
其中 l_i 、 r_i 为左右子编号（0表示无子节点，且不存在只有一个子节点的情况）；
若为非叶节点， f_i 是用于分裂的特征序号(1-based)， th_i 为阈值；
若为叶节点， f_i 与 th_i 置 0； label_i 表示当该节点作为叶子时的输出标签（0或1）。
接下来的 M 行：每行 K+1 个整数，前 K 个为该条验证样本的特征，最后一个为真实标签（0或1）。
输出描述
输出单行浮点数：在验证集上能达到的最大 F1 值，四舍五入到小数点后 6 位。

样例共 2 组

样例 1 · 路由规则：特征1≤50 进左子树，否则进右子树；在右子树中再按特征2≤70 判到左叶（输出0），否则到右叶（输出1）。 若不剪枝，五条样本的预测与真实标签对比如下：命中两条正类，出现两次“将负类判为正类”，未漏判正类，计算得 F1=2*2/(2*2+2+0)=0.666667。 尝试将右子树整体剪为叶（输出0）或将根剪为叶（输出0/1）等方案，F1 反而更低。因此最优为 0.666667。
输入
5 5 2
2 3 1 50 0
0 0 0 0 1
4 5 2 70 0
0 0 0 0 0
0 0 0 0 1
40 80 1
55 60 0
55 90 1
55 85 0
20 10 0
输出
0.666667
样例 2 · 路由规则：特征1≤30 走左子树（叶，输出0），否则进入右子树；在右子树内，特征2≤50 走左叶（输出1），否则走右叶（输出0）。 不剪枝时：TP=2（命中两条正类），FN=2（漏判两条正类），FP=0，F1=22/(4+0+2)=0.666667。 若把根节点直接剪成叶并输出1，则6条样本预测为1，其中TP=4（四条为正类），FP=2（两条为负类），FN=0，F1=24/(8+2+0)=0.800000。其他剪枝方案（如只剪右子树）得到的F1更低，因此最优为0.800000。
输入
5 6 2
2 3 1 30 1
0 0 0 0 0
4 5 2 50 1
0 0 0 0 1
0 0 0 0 0
35 40 1
35 70 0
35 60 1
25 80 0
28 10 1
50 45 1
输出
0.800000

算法解析依据一般

考点：树

限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

参考方向：树

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

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

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

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

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

该范式的通法易错点

  • 递归深度过大导致爆栈。
  • 建树时父子关系方向搞反（把树当成有向图但遍历方向错）。
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。

样例解读

样例 1：输入 5 5 2 / 2 3 1 50 0 / 0 0 0 0 1 / 4 5 2 70 0 / 0 0 0 0 0 / 0 0 0 0 1 / 40 80 1 / 55 60 0 / 55 90 1 / → 输出 0.666667

路由规则：特征1≤50 进左子树，否则进右子树；在右子树中再按特征2≤70 判到左叶（输出0），否则到右叶（输出1）。

若不剪枝，五条样本的预测与真实标签对比如下：命中两条正类，出现两次“将负类判为正类”，未漏判正类，计算得 F1=2*2/(2*2+2+0)=0.666667。

尝试将右子树整体剪为叶（输出0）或将根剪为叶（输出0/1）等方案，F1 反而更低。因此最优为 0.666667。

样例 2：输入 5 6 2 / 2 3 1 30 1 / 0 0 0 0 0 / 4 5 2 50 1 / 0 0 0 0 1 / 0 0 0 0 0 / 35 40 1 / 35 70 0 / 35 60 1 / → 输出 0.800000

路由规则：特征1≤30 走左子树（叶，输出0），否则进入右子树；在右子树内，特征2≤50 走左叶（输出1），否则走右叶（输出0）。

不剪枝时：TP=2（命中两条正类），FN=2（漏判两条正类），FP=0，F1=22/(4+0+2)=0.666667。

若把根节点直接剪成叶并输出1，则6条样本预测为1，其中TP=4（四条为正类），FP=2（两条为负类），FN=0，F1=24/(8+2+0)=0.800000。其他剪枝方案（如只剪右子树）得到的F1更低，因此最优为0.800000。

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

本题来源：2025年秋招-华为-8月27号AI岗。

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