0968. Binary Tree Cameras

---

Given a binary tree, we install cameras on the nodes of the tree.

Each camera at a node can monitor its parent, itself, and its immediate children.

Calculate the minimum number of cameras needed to monitor all nodes of the tree.

Example 1:

Input: [0,0,null,0,0]
Output: 1
Explanation: One camera is enough to monitor all nodes if placed as shown.

Example 2:

Input: [0,0,null,0,null,0,null,null,0]
Output: 2
Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.

Note:

• The number of nodes in the given tree will be in the range [1, 1000].
• Every node has value 0.

---

解法1

从讨论区抄来的答案.

贪婪算法.

1. 如果我们在leaf设置camera, 那么可以覆盖leaf本身和其父节点.
2. 如果我们在leaf的parent设置camera, 那么可以覆盖parent, parent的parent, leaf 和leaf的兄弟节点(如果有).

可以看到, 方案2总是比方案1要好. 所以我们的做法就是找到leaf, 在它的parent设置camera, 然后标记已经被覆盖的节点, 继续找leaf.

/**
 * 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) {
        return (dfs(root) < 1 ? 1 : 0) + res;
    }

    // 如果当前为leaf,返回 0
    // 如果当前为leaf的parant, 返回1
    // 如果当前为空,或者其被覆盖但是没有设置camera
    public int dfs(TreeNode root) {
        if (root == null) return 2;
        int left = dfs(root.left), right = dfs(root.right);
        // 如果左右节点有leaf, 返回1, 并且在当前位置(相当于leaf的父节点)添加camera
        if (left == 0 || right == 0) {
            res++;
            return 1;
        }
        // 如果左右有leaf的父节点 (返回值为1), 那么返回2(当前节点已经被覆盖,将其父节点作为leaf进行计算)
        // 否则(左右节点的返回值都为2), 当前节点判定为leaf, 返回0
        return left == 1 || right == 1 ? 2 : 0;
    }
}