华为520机试第三题

更新一下，中午睡觉的时候忽然想到构建树就是自底向上的递归返回，可直接求解。代码删减了一下。

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

输入描述：

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

输出描述：

所需最小摄像头数。

思路

本想直接在字符串上操作求解；后来放弃了。 所以还是决定先创建一棵树，然后递归求解。

树建起来后面就好操作了，建树采用消融的方式：将'0##'变成一个‘#’放回字符串。重复这个方式直到 字符串只剩下一个‘#’，树就建成了。

接下来对树进行递归访问，递归确定三件事：

 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{
            TreeNode* n = new TreeNode(s[i]);
            st.push(n);
        }
    }
    auto root =  st.top();
    size_t result = root->need ? root->count + 1 : root->count;
    delTree(root);
    return result;
}