<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>

/**
 * 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) {}
 * };
 */

typedef TreeNode node;

class Solution {
    int ans;
    int n;
    node* root;
    map<node*,int> dis;
    set<node*> cam;
    set<node*> cov;

    map<node*,node*> par; 

    bool leaf(node* r){
        return r and !r->left and !r->right;
    }

    void count(node* r){
        if(!r) return;
        r->val = n;
        n++;
        if(r->left) par[r->left] = r;
        if(r->right) par[r->right] = r;
        count(r->left); count(r->right);

    }

    bool coveredSubtree(node* r){
        if(!r) return true;
        if(cov.find(r)==cov.end()) return false;
        return coveredSubtree(r->left) and coveredSubtree(r->right);
    }

    void removeCoveredSubtrees(node* r){
        if(!r) return;
        if(coveredSubtree(r->left)) r->left = nullptr;
        if(coveredSubtree(r->right)) r->right = nullptr;

        removeCoveredSubtrees(r->left);
        removeCoveredSubtrees(r->right);
    }

    void addParofLeaves(node* r){
        if(!r) return;

        if(leaf(r->left)){
            cam.insert(r); 
            cov.insert(r);
            cov.insert(r->left);
            if(r->right) cov.insert(r->right);
            if(r!=root) cov.insert(par[r]);            
        }
        if(leaf(r->right)){
            cam.insert(r);
            cov.insert(r);
            cov.insert(r->right); cov.insert(r);
            if(r->left) cov.insert(r->left);
            if(r!=root) cov.insert(par[r]); 
        }

        addParofLeaves(r->left);
        addParofLeaves(r->right);
    }

public:
    int minCameraCover(TreeNode* r){
        if(leaf(r)) return 1;
        root = r;
        n = 0;
        count(root);

        while(cov.size()<n){
            addParofLeaves(root);
            removeCoveredSubtrees(root);

            for(auto x : cov) cout << x->val << ' '; cout << '\n';

            if(leaf(root) and cov.find(root)==cov.end()){
                cam.insert(root);
                cov.insert(root);
            }

        }

        return cam.size();





        
    }
};
25400