点亮战争迷雾
2026 华为OD机试真题8月19日华为OD上机新系统考试真题 100 分题型
点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解
题目描述
有一张二叉树地图，每一个节点都被战争迷雾所覆盖。在二叉树节点上插上一个侦察守卫，可以照亮该节点自身以及它的父节点和它的子节点的战争迷雾。在每个节点上插上侦察守卫的成本并不一样，用 cost[i] 表示节点 i 上的成本，每个节点的成本是正整数。
要求：
- 所有的战争迷雾都被驱散。
- 所花费的总成本最小。
补充说明：
- 单个节点的成本，
1 <= cost[i] <= 100； - 节点总数量
<= 1000。
2026 华为OD机试真题8月19日华为OD上机新系统考试真题 100 分题型
点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解
输入描述
一行，一个层序遍历字符串（含首尾圆括号），空节点用 # 表示，例如 (5,1,10,2,8,#,3)。
输出描述
输出最小的总费用。
示例1
输入
(5,1,10,2,8,#,3)输出
4说明
最优方案：
- 在节点
2（成本1）和节点6（成本3）插上侦察守卫，总成本4- 节点
2覆盖2,1,4,5；节点6覆盖6,3；所有节点均被覆盖
示例2
输入
(3,1,1)输出
2说明
- 方案一：在节点
1插上侦察守卫，可照亮所有地图，成本是3- 方案二：在节点
2和节点3插上侦察守卫，可照亮所有地图，成本是 1+1=2- 因此，最低成本的方案是方案二，返回值是
2
解题思路
核心思想
这是二叉树上的最小代价覆盖问题。一个守卫可以覆盖自己、父节点和左右子节点。
对每个节点做树形 DP，维护三种状态：
wait：当前节点没有放守卫，当前节点暂时未被子节点覆盖，等待父节点覆盖。covered：当前节点没有放守卫，但已经被某个子节点的守卫覆盖。placed：当前节点放置守卫。
根节点没有父节点，因此最终答案不能取 wait，只能取 min(covered, placed)。
算法步骤
- 按层序字符串恢复二叉树，
#表示空节点。 - 后序遍历每个节点，先计算左右子树的三种状态。
- 当前节点放守卫时，左右子树可以取各自最小合法状态。
- 当前节点不放守卫但已覆盖时，至少一个孩子必须放守卫。
- 当前节点等待父节点覆盖时，左右孩子自身都必须已经被覆盖。
- 根节点不能等待父节点，返回
min(covered, placed)。
复杂度分析
设二叉树节点数为 n。
- 时间复杂度：
O(n) - 空间复杂度：
O(n)，主要来自递归栈和
版权声明：
作者：魔改工程师
链接：https://www.sylblog.xin/archives/837
文章版权归作者所有，未经允许请勿转载。
THE END
