<p>You are given the <code>root</code> 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.</p>

<p>Return <em>the minimum number of cameras needed to monitor all nodes of the tree</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/29/bst_cameras_01.png" style="width: 138px; height: 163px;" />
<pre>
<strong>Input:</strong> root = [0,0,null,0,0]
<strong>Output:</strong> 1
<strong>Explanation:</strong> One camera is enough to monitor all nodes if placed as shown.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/29/bst_cameras_02.png" style="width: 139px; height: 312px;" />
<pre>
<strong>Input:</strong> root = [0,0,null,0,null,0,null,null,0]
<strong>Output:</strong> 2
<strong>Explanation:</strong> 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.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of nodes in the tree is in the range <code>[1, 1000]</code>.</li>
	<li><code>Node.val == 0</code></li>
</ul>

class Solution {
public:
    vector<vector<int>> memo;
    int C(TreeNode* root, int state){
        if(root == nullptr) return 0;
        if(memo[root->val][state] != -1) return memo[root->val][state];
        if(state == 0){
            //not observed
            //put camera in this
            int a = 1 + C(root->left, 1) + C(root->right, 1);
            //put camera on left if left exists
            int b = INT_MAX;
            if(root->left)
                b = min(b, C(root->left, 2) + C(root->right, 0));
			//put camera on right if right exists
            if(root->right)
                b = min(b, C(root->right, 2)+C(root->left, 0));
            
                
                
            memo[root->val][state] = min(a,b);
            return memo[root->val][state];
        }else if(state == 1){
            //observed
            //children not observed
            int a = C(root->left, 0) + C(root->right, 0);
            
            //still put a camera here
            int b = 1 + C(root->left, 1) + C(root->right, 1);
            memo[root->val][state] = min(a,b);
            return memo[root->val][state];
        }else{
			//has a camera on it
            memo[root->val][state] = 1+C(root->left,1) + C(root->right, 1);
            return memo[root->val][state];
        }
    }
    int addNumbers(TreeNode* root, int start){
        if(root == nullptr) return start;
        root->val = start;
        int x = addNumbers(root->left,start+1);
        int y = addNumbers(root->right, x);
        return y+1;
    }
    int minCameraCover(TreeNode* root) {
        int total = addNumbers(root,0);
        memo = vector<vector<int>>(total, vector<int>(3,-1));
        return C(root, 0);
    }
};
22200