监控二叉树

题目

给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

具体思路

贪心思路：尽可能的将摄像头布置在叶子节点的父节点

• 设置三个指标0,1,2，分别表示覆盖、未覆盖、有摄像头;
• 如果是根节点，默认覆盖;
• 然后从底向上覆盖，判断左右;
• 后序遍历二叉树
  • 左或者右有摄像头，返回覆盖，因为这是向上遍历的
  • 左或者右有没覆盖，返回摄像头，并设置
    • 左右都没覆盖，返回有摄像头，并设置
  • 左右都覆盖，返回没覆盖

具体代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */

// 设置 0：未覆盖；1:覆盖；2:有摄像头
class Solution {
public:
    int count = 0;
    int minCameraCover(TreeNode* root) {
        if (backtracking(root) == 0)
            count++;
        return count;
    }

    int backtracking(TreeNode* node) {
        // 终止条件
        if (node == nullptr)
            return 1;
        int left = backtracking(node->left);
        int right = backtracking(node->right);
        if (left == 1 && right == 1)
            return 0;
        if (left == 0 || right == 0) {
            count++;
            return 2;
        }
        if (left == 2 || right == 2) {
            return 1;
        }
        return -1;
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    int res = 0;

    public int minCameraCover(TreeNode root) {
        int flag = traversal(root);
        return flag == -7 ? res + 1 : res;
    }

    // 安装摄像头（7)、被摄像头看到(1)、没有被摄像头看到(-7)、
    // 1. 左灯右无灯
    // 5. 左摄像头右无
    // 2. 左无灯右灯
    // 5. 右摄像头左无
    // 3. 左右均无灯
    // 4. 左右均有灯

    public int traversal(TreeNode root) {
        if (root.left == null && root.right == null) {
            return -7;
        }

        int left = 1;
        int right = 1;
        if (root.left != null) {
            left = traversal(root.left);
        }
        if (root.right != null) {
            right = traversal(root.right);
        }

        if (left == -7 || right == -7) { // 下方有一个位置没有摄像头：添加摄像头
            res++;
            return 7;
        } else if (left == 7 || right == 7) { // 左或者右有摄像头：返回被照到
            return 1;
        } else if (left == 1 && right == 1) {
            return -7;
        }
        return -7;
    }
}

实际上也可以在返回空节点时判断，改一下相关的条件即可；

最后返回的时候，不能乱写：

1. return flag == -7 ? res + 1 : res;
条件 flag == -7 为真，执行 ? 后面的部分：res + 1。

计算表达式的值：10 + 1，得到结果 11。

返回：函数将 11 这个计算结果返回。

res 变量的状态：res 变量本身没有被任何操作修改，它的值仍然是 10。

结论：这行代码完美地实现了“如果条件成立，就返回 res 加一之后的值”这个意图。

2. return flag == -7 ? res++ : res;
条件 flag == -7 为真，执行 ? 后面的部分：res++。

计算表达式的值：res++ (后自增) 的规则是，整个表达式的值等于 自增之前 的值。所以，这个表达式的值是 10。

返回：函数将 10 这个值返回。

执行副作用：在表达式的值被取出后，res 变量自身加一。现在 res 的值变成了 11。

结论：这行代码存在严重逻辑错误！ 它返回的是 res 的原始值，而对 res 的修改对于函数的返回值来说已经太晚了。调用者会收到 10，而不是期望的 11。

这个的摄像头最后实际上是装到根节点的