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

题目描述

一座重要建筑的安保系统被设计成一个树形结构，每个节点代表一个安保传感器。
每个传感器都有一个特定的警戒值，并且可以被激活或关闭。
为了防止信号干扰，系统有一个严格的规定：
如果一个传感器被激活，那么与它直接相连的所有传感器（即它的父节点和子节点）都必须保持关闭状态。
作为安保系统的总工程师，您需要制定一个传感器激活方案，使得整个安保系统的总警戒值达到最大。
安保系统的拓扑结构是一个二叉树，由一个层序遍历的数组表示。
数组中的每个元素值代表对应传感器的警戒值。
您的任务是计算在该激活规则下，所能获得的最大总警戒值是多少。

输入输出

输入描述
第一行为一个整数 N ，代表层序遍历数组的大小。
第二行为 N 个整数，代表层序遍历的数组，用空格分隔。
关于层序遍历的说明：
输入数组是二叉树的层序遍历结果。从根节点开始，自上而下、从左到右逐层记录每个节点的警戒值。如果某个位置在结构上应该有节点但实际没有（即 `null` 节点），则用 `0` 来占位。
数据范围：
1 ≤ N ≤ 10^6
0 ≤ 警戒值 ≤ 100
输出描述
输出一个整数，表示能够获得的最大总警戒值。

样例共 1 组

样例 1
输入
18
78 44 73 98 54 51 0 0 27 0 53 87 34 0 0 0 0 40
输出
391

算法解析依据一般

考点：树

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

题目画像

  • 数据规模：N ≤ 1e6
  • 复杂度门槛：只允许 O(n) 或 O(n log n)，且常数要小（注意读入效率）。
  • 源站时限：3 秒（牛客口径，非本题专属门槛）

解题思路

参考方向：树

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

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

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

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

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

该范式的通法易错点

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

对照本题

  • 数据规模 N ≤ 1e6，只允许 O(n) 或 O(n log n)，且常数要小（注意读入效率）。
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。

样例

样例 1

  • 输入：18 / 78 44 73 98 54 51 0 0 27 0 53 87 34 0 0 0 0 40
  • 输出：391

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

本题来源：2025年秋招-华为-10月15号开发岗。

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