Binary Tree Cameras Solutions in C++

/// Source : https://leetcode.com/problems/binary-tree-cameras/
/// Author : liuyubobobo
/// Time   : 2019-03-17

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;


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

/// Memory Search
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {

private:
    unordered_map<TreeNode*, int> indexes;

public:
    int minCameraCover(TreeNode* root) {

        if(!root) return 0;

        indexes.clear();
        tagIndexes(root, indexes);

        vector<int> dp(indexes.size() * 4, -1);
        return dfs(root, false, true, dp);
    }

private:
    int dfs(TreeNode* root, bool isCamera, bool needToCover, vector<int>& dp){

        if(!root) return 0;

        int index = indexes[root];
        int hashcode = index * 4 + isCamera * 2 + needToCover;

        if(dp[hashcode] != -1) return dp[hashcode];

        int res;
        if(isCamera){
            res = dfs(root->left, false, false, dp) + dfs(root->right, false, false, dp);
        }
        else{
            res = 1 + dfs(root->left, false, false, dp) + dfs(root->right, false, false, dp);
            if(!needToCover)
                res = min(res, dfs(root->left, false, true, dp) + dfs(root->right, false, true,dp));
            else{
                if(root->left)
                    res = min(res, 1 + dfs(root->left, true, false, dp) + dfs(root->right, false, true, dp));
                if(root->right)
                    res = min(res, 1 + dfs(root->right, true, false, dp) + dfs(root->left, false, true, dp));
                if(root->left && root->right)
                    res = min(res, 2 + dfs(root->left, true, false, dp) + dfs(root->right, true, false, dp));
            }
        }

        return dp[hashcode] = res;
    }

    void tagIndexes(TreeNode* root, unordered_map<TreeNode*, int>& indexes){

        if(!root) return;

        int index = indexes.size();
        indexes[root] = index;

        tagIndexes(root->left, indexes);
        tagIndexes(root->right, indexes);
    }
};

int main() {

    TreeNode* root1 = new TreeNode(0);
    root1->left = new TreeNode(0);
    root1->left->left = new TreeNode(0);
    root1->left->right = new TreeNode(0);
    cout << Solution().minCameraCover(root1) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/binary-tree-cameras/
/// Author : liuyubobobo
/// Time   : 2019-03-17

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;


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


/// Memory Search - Tree DP
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {

public:
    int minCameraCover(TreeNode* root) {

        if(!root) return 0;
        // isCamera, needToeCover - 00, 01, 10, 11
        vector<int> res = dfs(root);
        return res[0 * 2 + 1];
    }

private:
    vector<int> dfs(TreeNode* root){

        if(!root) return {0, 0, 0, 0};

        vector<int> lres = dfs(root->left);
        vector<int> rres = dfs(root->right);

        vector<int> res(4);
        // 10 and 11
        res[1 * 2 + 0] = res[1 * 2 + 1] = lres[0 * 2 + 0] + rres[0 * 2 + 0];

        // 00 and 01
        res[0 * 2 + 0] = res[0 * 2 + 1] = 1 + lres[0 * 2 + 0] + rres[0 * 2 + 0];

        // 00
        res[0 * 2 + 0] = min(res[0 * 2 + 0], lres[0 * 2 + 1] + rres[0 * 2 + 1]);

        // 01
        if(root->left)
            res[0 * 2 + 1] = min(res[0 * 2 + 1], 1 + lres[1 * 2 + 0] + rres[0 * 2 + 1]);
        if(root->right)
            res[0 * 2 + 1] = min(res[0 * 2 + 1], 1 + lres[0 * 2 + 1] + rres[1 * 2 + 0]);
        if(root->left && root->right)
            res[0 * 2 + 1] = min(res[0 * 2 + 1], 2 + lres[1 * 2 + 0] + rres[1 * 2 + 0]);

        return res;
    }
};


int main() {

    TreeNode* root1 = new TreeNode(0);
    root1->left = new TreeNode(0);
    root1->left->left = new TreeNode(0);
    root1->left->right = new TreeNode(0);
    cout << Solution().minCameraCover(root1) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/binary-tree-cameras/
/// Author : liuyubobobo
/// Time   : 2019-03-18

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;


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


/// Memory Search - Tree DP
/// Using 3 states instead of 4 states (3 states is enough)
///
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {

public:
    int minCameraCover(TreeNode* root) {

        if(!root) return 0;
        vector<int> res = dfs(root);
        return res[2];
    }

private:
    /// State 0: install a camera
    /// State 1: not install a camera but do not need to be covered
    /// State 2: not install a camera but do need to be covered
    vector<int> dfs(TreeNode* root){

        if(!root) return {0, 0, 0};

        vector<int> lres = dfs(root->left);
        vector<int> rres = dfs(root->right);

        vector<int> res(3);

        res[0] = lres[1] + rres[1];

        res[1] = res[2] = 1 + lres[1] + rres[1];
        res[1] = min(res[1], lres[2] + rres[2]);

        if(root->left)
            res[2] = min(res[2], 1 + lres[0] + rres[2]);
        if(root->right)
            res[2] = min(res[2], 1 + lres[2] + rres[0]);
        if(root->left && root->right)
            res[2] = min(res[2], 2 + lres[0] + rres[0]);

        return res;
    }
};


int main() {

    TreeNode* root1 = new TreeNode(0);
    root1->left = new TreeNode(0);
    root1->left->left = new TreeNode(0);
    root1->left->right = new TreeNode(0);
    cout << Solution().minCameraCover(root1) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/binary-tree-cameras/
/// Author : liuyubobobo
/// Time   : 2019-03-18

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;


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


/// Greedy
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {

private:
    int res;
    unordered_set<TreeNode*> set;

public:
    int minCameraCover(TreeNode* root) {

        res = 0;
        set.clear();
        dfs(root, NULL);
        return res ? res : 1;
    }

private:
    void dfs(TreeNode* root, TreeNode* parent){

        if(!root) return;

        dfs(root->left, root);
        dfs(root->right, root);

        if((!root->left || set.count(root->left)) && (!root->right || set.count(root->right))){
            if(!set.count(root) && !parent) res ++;
            return;
        }

        if((root->left && !set.count(root->left)) ||
           (root->right && !set.count(root->right))) {
            res++;
            if (root->left) set.insert(root->left);
            if (root->right) set.insert(root->right);
            set.insert(root);
            if (parent) set.insert(parent);
        }
        return;
    }
};


int main() {

    TreeNode* root1 = new TreeNode(0);
    root1->left = new TreeNode(0);
    root1->left->left = new TreeNode(0);
    root1->left->right = new TreeNode(0);
    cout << Solution().minCameraCover(root1) << endl;
    // 1


    TreeNode* root2 = new TreeNode(0);
    root2->right = new TreeNode(0);
    root2->right->right = new TreeNode(0);
    root2->right->right->right = new TreeNode(0);
    cout << Solution().minCameraCover(root2) << endl;
    // 2

    TreeNode* root3 = new TreeNode(0);
    root3->left = new TreeNode(0);
    root3->right = new TreeNode(0);
    root3->right->right = new TreeNode(0);
    cout << Solution().minCameraCover(root3) << endl;
    // 2

    return 0;
}