题面描述

给定一棵 二叉树，树上每个节点代表一户居民。需要在若干节点上建设基站，每个基站可以覆盖其所在节点及与其相邻的左右子节点和父节点，覆盖距离为 $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) 本身不放，但要被覆盖，必有“相邻”节点放基站。
• 两种覆盖来源：
  1. 左子节点放（状态 0），此时右子节点只需“不放但已被覆盖”（状态 1）或“放”（状态 0），保证右侧也不会遗漏。
  2. 右子节点放（状态 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$个基站可以覆盖所有节点(左右两种方案都能覆盖所有的节点)