20260819-点亮战争迷雾（N0062）- 算法机考高频题型 · 华为OD / 树题解 | AlgoMooc

N0062. 20260819-点亮战争迷雾

困难

通过率 83% · 提交 6 · 通过 5

200分华为OD树DFSDP

本题改编自算法机考高频题型 · 考点：200分 / 华为OD · 难度：困难

有一张二叉树地图，每一个节点都被战争迷雾所覆盖。在二叉树节点上插上一个侦察守卫，可以照亮该节点自身以及它的父节点和它的子节点的战争迷雾。在每个节点上插上侦察守卫的成本并不一样，用 cost [i] 表示节点 i 上的成本，每个节点的成本是正整数。要求：

所有的战争迷雾都被驱散。
所花费的总成本最小。

补充说明：

单个节点的成本，1 ≤ cost[i] ≤ 100；
节点总数量 ≤ 1000。

这类题属于算法机考高频题型中「200分 / 华为OD」方向的高频题型，通常考察对「200分 / 华为OD」的建模能力与边界条件处理。掌握本题的解题思路后，可举一反三应对同类真题方向，稳步提升机考通过率。

输入描述

一个Node类型的参数，二叉树的根节点。

构建二叉树使用一个层序遍历字符串来构建，空节点用 # 表示，例如 (5,1,10,2,8,#,3)。

输出描述

输出最小的总费用。

示例

示例 1

输入示例

5,1,10,2,8,#,3

输出示例

说明：

树结构图如下

              1(5)
            /   \
           2(1)  3(10)
          / \     \
         4(2) 5(8) 6(3)

最优方案：

在节点 2（成本 1）和节点 6（成本 3）插上侦察守卫，总成本 4
节点 2 覆盖 2,1,4,5；节点 6 覆盖 6,3；所有节点均被覆盖

示例 2

输入示例

3,1,1

输出示例

说明：

树结构图如下 1(3) /
2(1) 3(1)

方案一：在节点 1 插上侦察守卫，可照亮所有地图，成本是 3
方案二：在节点 2 和节点 3 插上侦察守卫，可照亮所有地图，成本是 1 + 1 = 2
因此，最低成本的方案是方案二，返回值是 2

时间限制 1000 ms · 内存限制 256 MB

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

问小欧 · 图解算法年卡¥99 开通 →

字号13Ctrl+/ 注释 · Ctrl+↵ 提交

class Node:
    def __init__(self, cost: int):
        self.cost = cost
        self.left = None
        self.right = None

# 代码中的类名、方法名、参数名已经指定
# @param root 二叉树的根节点
# @return 最小的总费用
class Solution:
    def minCameraCover(self, root: Node) -> int:
        pass

# 以下内容为LeetCode核心代码模式转为ACM模式所需代码
# 请在algomooc oj上直接使用，在实际考试中无需编写

def build_tree(s: str):
    if not s:
        return None
    parts = s.split(',')
    if parts[0] == '#':
        return None
    root = Node(int(parts[0]))
    queue = [root]
    i = 1
    while queue and i < len(parts):
        node = queue.pop(0)
        if i < len(parts) and parts[i] != '#':
            node.left = Node(int(parts[i]))
            queue.append(node.left)
        i += 1
        if i < len(parts) and parts[i] != '#':
            node.right = Node(int(parts[i]))
            queue.append(node.right)
        i += 1
    return root

if __name__ == '__main__':
    s = input().strip()
    root = build_tree(s)
    sol = Solution()
    print(sol.minCameraCover(root))

class Node:
    def __init__(self, cost: int):
        self.cost = cost
        self.left = None
        self.right = None

# 代码中的类名、方法名、参数名已经指定
# @param root 二叉树的根节点
# @return 最小的总费用
class Solution:
    def minCameraCover(self, root: Node) -> int:
        pass

# 以下内容为LeetCode核心代码模式转为ACM模式所需代码
# 请在algomooc oj上直接使用，在实际考试中无需编写

def build_tree(s: str):
    if not s:
        return None
    parts = s.split(',')
    if parts[0] == '#':
        return None
    root = Node(int(parts[0]))
    queue = [root]
    i = 1
    while queue and i < len(parts):
        node = queue.pop(0)
        if i < len(parts) and parts[i] != '#':
            node.left = Node(int(parts[i]))
            queue.append(node.left)
        i += 1
        if i < len(parts) and parts[i] != '#':
            node.right = Node(int(parts[i]))
            queue.append(node.right)
        i += 1
    return root

if __name__ == '__main__':
    s = input().strip()
    root = build_tree(s)
    sol = Solution()
    print(sol.minCameraCover(root))

写完代码点「提交」，将对全部测试用例判题。

输入描述

输出描述

示例

我的提交