华为 · 树 · 算法编程题
华为 树 N ≤ 2000 时限 1 秒 / 512 MB

题目描述

小红正在为电商平台部署一个交易风险识别服务。离线训练得到的随机森林由 T 棵二叉决策树组成，每笔交易包含 M 个整数特征。
一棵树从编号为 1 的根节点开始预测。内部节点保存特征编号 idx 、阈值 val 和左右子节点编号：如果当前交易的第 idx 个特征值小于或等于 val ，则进入左子节点，否则进入右子节点。到达叶子节点后，该树输出标签 0 或 1 。
森林采用多数表决：如果输出 1 的树严格多于输出 0 的树，最终结果为 1 ；票数相同时，最终结果为 0 。
请依次输出 N 笔交易的预测结果。

输入输出

输入描述
第一行输入三个整数 T,M,N ，分别表示决策树数量、特征维数和交易数量。
接下来依次输入 T 棵树。每棵树先输入一个整数 K ，随后输入 K 行节点信息，节点按编号 1 到 K 给出。
输入 1,idx,val,left,right 表示内部节点；输入 0,label 表示叶子节点。
最后输入 N 行，每行包含 M 个整数，表示一笔交易的特征。
保证 1 ≤ T ≤ 51 ， 1 ≤ M ≤ 50 ， 1 ≤ N ≤ 2000 ， 1 ≤ K ≤ 500 。特征值和阈值均在 [-10^5,10^5] 内。所有树结构合法、无环，每个内部节点都有两个有效子节点。
输出描述
输出 N 行，每行一个整数 0 或 1 ，表示对应交易的预测结果。

样例共 1 组

样例 1 · 三笔交易得到的三棵树投票分别为 0,1,1、1,1,1 和 0,0,1。
输入
3 2 3
3
1 1 5 2 3
0 0
0 1
3
1 2 4 2 3
0 1
0 0
1
0 1
3 2
8 2
3 9
输出
1
1
0

算法解析依据一般

考点：树

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

题目画像

  • 数据规模：N ≤ 2000，K ≤ 500，T ≤ 51，M ≤ 50
  • 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

参考方向：树

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

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

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

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

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

该范式的通法易错点

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

对照本题

  • 数据规模 N ≤ 2000，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。

样例解读

样例 1：输入 3 2 3 / 3 / 1 1 5 2 3 / 0 0 / 0 1 / 3 / 1 2 4 2 3 / 0 1 / 0 0 / 1 / 0 1 / 3 2 / 8 2 / 3 9 → 输出 1 / 1 / 0

三笔交易得到的三棵树投票分别为 0,1,1、1,1,1 和 0,0,1。

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

本题来源：2026年-华为-05月22号AI岗。

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