Binary Tree Cameras

바이너리 트리가 주어지고 특정 노드에

부모 노드, 자기 자신, 자식을 커버하는 카메라를 설치한다고 한다.

바이너리 트리를 모두 커버할 때 카메라의 최소 개수를 구하는 문제이다.

노드의 val 값은 모두 0이라고 주어져 해당 값의 수정을 통해 조건을 체크 했다.

/**
 * 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:
    static const int NOT_COVERED = 0;
    static const int INSTALED = 1;
    static const int COVERED = 2;
    
    int installedCamera{};
    
    void CheckCondition(TreeNode *now, TreeNode *next)
    {
        switch (next->val)
        {
            case INSTALED:
                {
                    now->val = COVERED;
                }
                break;
                
            case NOT_COVERED:
                {
                    now->val = INSTALED;
                    next->val = COVERED;
                    installedCamera++;
                }
                break;
                
            default:
                break;
        }
    }
    
    void InstallCamera(TreeNode *node)
    {
        if (node->left != NULL)
        {
            InstallCamera(node->left);
            CheckCondition(node, node->left);
        }
        
        if (node->right != NULL && node->val != INSTALED)
        {
            InstallCamera(node->right);
            CheckCondition(node, node->right);
        }
        else if (node->right != NULL && node->val == INSTALED)
        {
            InstallCamera(node->right);
        }
    }
    
    int minCameraCover(TreeNode* root) {
        
        installedCamera = 0;
        
        InstallCamera(root);
        if (root->val == NOT_COVERED)
        {
            installedCamera++;
        }
        
        return installedCamera;
        
    }
};