一个街区为了提高街区安全性，需要在街区的路灯上安装若干摄像头，用一个二叉树表示街区的路灯。 每个节点表示一个路灯，在路灯上安装摄像头。每个摄像头可以监控其自身、父对象和直接子对象。 为保证每个路灯都被监控，请计算所需的最小摄像头数。

输入描述：

输入一串字符，代表由前序排列的二叉树表示的路灯，字符由'0'和'#'组成，每个'0'表示一个要监控的路灯， '#'表示子节点为空

输出描述：

所需最小摄像头数。

思路

构建二叉树采用消融的方式：将'0##'变成一个‘#’放回字符串。重复这个方式直到 字符串只剩下一个‘#’，树就建成了。

建树的过程实际上是一个递归返回的过程，和我们递归遍历一棵树是等价的。 因此，可以把求解的过程和建树一同进行。每找到一棵树[既0##]：

1. 确定子树放的路灯数量；
2.确定子树需不需要父节点帮忙放路灯
3.确定子树的根有没有放路灯，从而决定自己需不需要放。 
 struct TreeNode {
      char val;
      char tag;
      bool need;
      bool put;
      size_t count;
      TreeNode *left, *right;
      TreeNode(char x) : val(x), tag(x), 
                left(NULL), right(NULL),
                need(false), put(false), count(0){}
};

void delTree(TreeNode* root){
    queue<TreeNode*> fifo;
    fifo.push(root);
    while(!fifo.empty()){
        TreeNode* node = fifo.front();
        if(node){
            fifo.push(node->left);
            fifo.push(node->right);
            delete node;
        }
        fifo.pop();
    }
}

size_t makeTree(string s){
    stack<TreeNode*> st;
    for(int i = 0; i < s.size();++i){
        if(!st.empty() && (s[i] == '#' && st.top()->tag == '#')){
            TreeNode* r = new TreeNode('#');
            while(!st.empty() && st.top()->tag == '#'){
                TreeNode* l = st.top();
                st.pop();
                TreeNode* root = st.top();
                st.pop();
                root->left = l;
                root->right = r;
                root->tag = '#';

                root->count += l->count;
                root->count += r->count;

                if(l->need || r->need){
                    root->count += 1;
                    root->put = true;
                    root->need = false;
                }else if(l->put || r->put){
                    root->need = false;
                    root->put = false;
                }else{
                    root->put = false;
                    root->need = true;
                }
                r = root;
            }
            st.push(r);
        }else{
            st.push(new TreeNode(s[i]));
        }
    }
    auto root =  st.top();
    size_t result = root->need ? root->count + 1 : root->count;
    delTree(root);
    return result;
}