最少基站覆盖二叉树问题

---

💡 问题描述

给定一棵二叉树，每个节点上住了一户居民。现在要在树上建设通信基站。

规则如下：

• 每个基站可以覆盖它自身和相邻的节点（父节点、左孩子、右孩子）。
• 我们需要在保证所有节点被信号覆盖的前提下，最少建设基站数目。

---

📥 输入描述

一行由空格分隔的字符串表示的节点值构成的数组 nums，表示一棵二叉树的层序遍历结果。

• 每个元素是一个正整数，表示节点值；
• 若节点不存在，则用 "N" 表示。

示例输入：

1 2 3 4 N 5 6

---

📤 输出描述

输出一个整数，表示最少需要建设的基站个数。

示例输出：

2

---

🧠 解题思路（超详细讲解）

这是一个典型的 树形 DP（动态规划） 问题。我们可以使用后序遍历（递归） + 状态定义来解决。

---

🌳 状态定义

对每个节点 u，我们定义三种状态：

状态	含义
f[u][0]	在节点 u 放置基站，覆盖其子树最少基站数
f[u][1]	不在 u 放置基站，且 u 已被覆盖（如子节点有基站）
f[u][2]	不在 u 放置基站，且 u 未被覆盖，需要父节点来覆盖

---

🔁 状态转移

假设节点 u 的左孩子为 l，右孩子为 r，则有如下转移：

1️⃣ f[u][0]: 自己放基站

放一个基站可以覆盖自己、父节点、左右子节点。

所以左右子节点可以处于任何状态，我们选择最优的（即三者中最小值）：

$$f[u][0]=1+\min (f[l][0],f[l][1],f[l][2])+\min (f[r][0],f[r][1],f[r][2])$$

---

2️⃣ f[u][1]: 不放但被覆盖

此时，至少有一个子节点放了基站。我们考虑两种情况并取最小值：

• 左子节点放了基站，右边可以是已覆盖或放基站：

  $$f[l][0]+\min (f[r][0],f[r][1])$$

• 右子节点放了基站，左边可以是已覆盖或放基站：

  $$f[r][0]+\min (f[l][0],f[l][1])$$

因此：

$$f[u][1]=\min \left(f[l][0]+\min (f[r][0],f[r][1]),f[r][0]+\min (f[l][0],f[l][1])\right)$$

---

3️⃣ f[u][2]: 不放也没被覆盖（等待父节点）

为了不出现盲区，左右子节点必须已经被覆盖：

$$f[u][2]=f[l][1]+f[r][1]$$

---

🟨 边界条件：空节点如何处理？

对于空节点（即 "N"），我们返回：

{INF, 0, 0}

含义：

• f[0] = INF：因为空节点不能放基站（不合法）；
• f[1] = 0：已经被覆盖，空节点不需要覆盖；
• f[2] = 0：等待父节点覆盖也是允许的（也不需要覆盖）。

---

✅ 代码实现（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:
    // 后序遍历，每个节点返回三种状态
    array<int, 3> dfs(TreeNode* u) {
        if (!u) return {INF, 0, 0}; // 空节点的三种状态

        auto L = dfs(u->left);  // 左子树结果
        auto R = dfs(u->right); // 右子树结果

        array<int, 3> f;

        // 状态0：自己放基站
        f[0] = 1 + min({L[0], L[1], L[2]}) + min({R[0], R[1], R[2]});

        // 状态1：不放但被覆盖（子节点放了基站）
        f[1] = min(
            L[0] + min(R[0], R[1]),
            R[0] + min(L[0], L[1])
        );

        // 状态2：不放且未被覆盖（等待父节点）
        f[2] = L[1] + R[1];

        return f;
    }

    int minStation(TreeNode* root) {
        auto res = dfs(root);
        return min(res[0], res[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* node = q.front(); q.pop();
        if (nums[i] != "N") {
            node->left = new TreeNode(stoi(nums[i]));
            q.push(node->left);
        }
        i++;
        if (i < nums.size() && nums[i] != "N") {
            node->right = new TreeNode(stoi(nums[i]));
            q.push(node->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;
}

---

📌 示例说明

输入：

1 2 3 4 N 5 6

构建的树结构如下：

       1
     /   \
    2     3
   /     / \
  4     5   6

最优放置方式：

• 在节点 2 放一个基站
• 在节点 3 放一个基站

这样可以覆盖所有节点，只需 2 个基站。

输出：

2

---

⏱️ 复杂度分析

• 时间复杂度：$O(n)$，每个节点只遍历一次；
• 空间复杂度：$O(h)$，递归栈空间，最坏情况下为树的高度。

---

📚 总结

• 这是典型的树上 DP 问题；
• 三个状态模型很常见：放、不放但被覆盖、不放也没被覆盖；
• 后序遍历 + 动态规划是处理树结构问题的利器；
• 注意空节点的处理策略是关键。