Leetcode 968: Binary Tree Cameras

You are given the root of a binary tree. We install cameras on the tree nodes where each camera at a node can monitor its parent, itself, and its immediate children.

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

Example 1:

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

Example 2:

Input: root = [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.

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• Node.val == 0

Problem Analysis:

It seems to use dynamic programming. But here we can use greedy algorithm.

If a node is leaf node, then the camera can put on the parent node; If left child node and right child node are all having a camera, then parent node don’t need to install a camera. Or parent node need to install a camera.

Then we can iterate the tree with post order, and get how many cameras we need to install.

Note that if the tree is only one node, the camera number is 1.

Solution

/**
 * 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) {}
 * };
 */
class Solution {
public:
    int minCameraCover(TreeNode* root) {
        return (dfs(root) < 1 ? 1 : 0) + res_;
    }

private:
    // return 1 means the node need to install a camera,
    // return 0 means don't need to install,
    // return 2 means unable to install
    int dfs(TreeNode* root) {
        if (!root) return 2;
        int left = dfs(root->left);
        int right = dfs(root->right);
        if (left == 0 || right == 0) {
            ++res_;
            return 1;
        }

        return left == 1 || right == 1 ? 2 : 0;
    }
private:
    int res_{0};
};

Time complexity is O(n)

Space complexity is O(1)