#P2927. 第2题-建设基站
-
1000ms
Tried: 1146
Accepted: 227
Difficulty: 5
所属公司 :
华为
时间 :2025年5月7日-暑期实习
-
算法标签>树形dp
第2题-建设基站
题面描述
给定一棵 二叉树,树上每个节点代表一户居民。需要在若干节点上建设基站,每个基站可以覆盖其所在节点及与其相邻的左右子节点和父节点,覆盖距离为 1。求覆盖整棵树的最少基站数量。
思路
对每个节点 u,定义三种状态:
- f[u][0]:在节点 u 放置基站,覆盖整棵子树所需的最少基站数。
- f[u][1]:不在节点 u 放置基站,且节点 u 已被覆盖(由子节点或父节 点的基站覆盖)。
- f[u][2]:不在节点 u 放置基站,且节点 u 未被覆盖,等待其父节点来覆盖。
设节点 u 的左、右孩子为 l 和 r,则有转移:
1.放基站:

- “1”:在节点 (u) 自身放一个基站。
- 子树贡献:既然基站能覆盖父节点和所有相邻子节点,无论左/右子节点的覆盖情况如何,都已经被 (u) 的基站覆盖了,所以子节点可以自由选择最优状态(放、不放但已覆盖、不放且未覆盖)来最小化总数。
- 因此,左右子树各取三种状态中的最小值。
2.已被覆盖且不放:

- 前提:(u) 本身不放,但要被覆盖,必有“相邻”节点放基站。
- 两种覆盖来源:
- 左子节点放(状态 0),此时右子节点只需“不放但已被覆盖”(状态 1)或“放”(状态 0),保证右侧也不会遗漏。
- 右子节点放(状态 0),对称地左子节点取 0 或 1。
- 取以上两种方案中更小者。
注意:这里只考虑子节点覆盖的情况,因为「父节点放」的覆盖会在递归回溯到父时处理,不必在子树内枚举。
3.未被覆盖且不放:

- 前提:(u) 自身不放,又不被子节点覆盖,必须等待父节点来覆盖。
- 子节点要保证“已覆盖”,否则子节点若也未被覆盖,既无自身基站,又没人覆盖,就会死角。
- 因此左右子节点都只能处于“已被覆盖”(状态 1)。
边界说明
- 对于空节点(null):
- 当作 已覆盖,因为它不需要覆盖也不会产生盲区:

- “放基站”状态无意义,设为极大值:
。
- 当作 已覆盖,因为它不需要覆盖也不会产生盲区:
这样,三条转移就能完整描述所有可能的放/不放、被/未被覆盖组合,递归合并后保证全局最优。
时间复杂度 O(n),空间复杂度 O(h)。
C++
#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};
const int INF = 1e9;
class Solution {
public:
// dfs 返回长度为 3 的数组:f0, f1, f2
array<int,3> dfs(TreeNode* u) {
if (!u) {
// 空节点:放基站不可能(无限大),已覆盖/未覆盖均为 0
return {INF, 0, 0};
}
auto L = dfs(u->left);
auto R = dfs(u->right);
array<int,3> f;
// f[u][0]
f[0] = 1 + min({L[0],L[1],L[2]}) + min({R[0],R[1],R[2]});
// f[u][1]
f[1] = min(
L[0] + min(R[0], R[1]),
R[0] + min(L[0], L[1])
);
// f[u][2]
f[2] = L[1] + R[1];
return f;
}
int minStation(TreeNode* root) {
auto f = dfs(root);
// 根节点取 0 或 1
return min(f[0], f[1]);
}
};
// 层序建树
TreeNode* buildTree(const vector<string>& nums) {
if (nums.empty() || nums[0]=="N") return nullptr;
TreeNode* root = new TreeNode(stoi(nums[0]));
queue<TreeNode*> q; q.push(root);
int i = 1;
while (i < nums.size()) {
TreeNode* cur = q.front(); q.pop();
if (nums[i] != "N") {
cur->left = new TreeNode(stoi(nums[i]));
q.push(cur->left);
}
i++;
if (i < nums.size() && nums[i] != "N") {
cur->right = new TreeNode(stoi(nums[i]));
q.push(cur->right);
}
i++;
}
return root;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<string> nums;
string s;
while (cin >> s) nums.push_back(s);
TreeNode* root = buildTree(nums);
Solution sol;
cout << sol.minStation(root);
return 0;
}
Python
# 定义二叉树节点
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
import sys
sys.setrecursionlimit(10000)
class Solution:
def dfs(self, u):
if not u:
# 空节点:放基站无限大,已覆盖/未覆盖为 0
return float('inf'), 0, 0
L0, L1, L2 = self.dfs(u.left)
R0, R1, R2 = self.dfs(u.right)
# f[u][0]
f0 = 1 + min(L0, L1, L2) + min(R0, R1, R2)
# f[u][1]
f1 = min(L0 + min(R0, R1), R0 + min(L0, L1))
# f[u][2]
f2 = L1 + R1
return f0, f1, f2
def minStation(self, root):
f0, f1, _ = self.dfs(root)
return min(f0, f1)
# 层序建树
from collections import deque
def buildTree(nums):
if not nums or nums[0]=='N':
return None
root = TreeNode(int(nums[0]))
q = deque([root])
i = 1
while i < len(nums):
node = q.popleft()
if nums[i] != 'N':
node.left = TreeNode(int(nums[i]))
q.append(node.left)
i += 1
if i < len(nums) and nums[i] != 'N':
node.right = TreeNode(int(nums[i]))
q.append(node.right)
i += 1
return root
if __name__ == '__main__':
nums = sys.stdin.read().split()
root = buildTree(nums)
print(Solution().minStation(root))
Java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private static final int INF = 1000000000;
// 返回长度为3的数组:f0,f1,f2
public int[] dfs(TreeNode u) {
if (u == null) {
// 空节点
return new int[]{INF, 0, 0};
}
int[] L = dfs(u.left);
int[] R = dfs(u.right);
int[] f = new int[3];
// f0
f[0] = 1 + Math.min(Math.min(L[0],L[1]),L[2])
+ Math.min(Math.min(R[0],R[1]),R[2]);
// f1
f[1] = Math.min(
L[0] + Math.min(R[0],R[1]),
R[0] + Math.min(L[0],L[1])
);
// f2
f[2] = L[1] + R[1];
return f;
}
public int minStation(TreeNode root) {
int[] f = dfs(root);
return Math.min(f[0], f[1]);
}
// 层序建树
public static TreeNode buildTree(List<String> nums) {
if (nums.isEmpty() || nums.get(0).equals("N")) return null;
TreeNode root = new TreeNode(Integer.parseInt(nums.get(0)));
Queue<TreeNode> q = new LinkedList<>(); q.offer(root);
int i = 1;
while (i < nums.size()) {
TreeNode cur = q.poll();
if (!nums.get(i).equals("N")) {
cur.left = new TreeNode(Integer.parseInt(nums.get(i)));
q.offer(cur.left);
}
i++;
if (i < nums.size() && !nums.get(i).equals("N")) {
cur.right = new TreeNode(Integer.parseInt(nums.get(i)));
q.offer(cur.right);
}
i++;
}
return root;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
List<String> nums = new ArrayList<>();
while (sc.hasNext()) nums.add(sc.next());
TreeNode root = buildTree(nums);
System.out.println(new Solution().minStation(root));
}
}
题目内容
有一棵二叉树,每个节点上都住了一户居民。现在要给这棵树上的居民建设基站,每个基站只能覆盖她所在与相邻的节点,请问信号覆盖这棵树最少需要建设多少个基站
输入描述
一个整数数组nums(1<=num.length<=3000),用空格分隔,表示二叉树的节点值,正整数表示存在节点,N表示不存在节点,如[1 2 3 4 N 5 6]表示一颗如下所示的树,最少需要建设2个基站
输出描述
最少需要建设的基站个数
样例1
输入
1 2 3 4 N 5 6
输出
2
说明
如图,2个基站可以覆盖所有节点

样例2
输入
1 2 N 3 N N 4
输出
2
说明
如图,2个基站可以覆盖所有节点(左右两种方案都能覆盖所有的节点)
