街区路灯问题【二叉树】
一个街区为了提高街区安全性，需要在街区的路灯上安装若干摄像头，用一个二叉树表示街区的路灯。 每个节点表示一个路灯，在路灯上安装摄像头。每个摄像头可以监控其自身、父对象和直接子对象。 为保证每个路灯都被监控，请计算所需的最小摄像头数。
输入描述：
输入一串字符，代表由前序排列的二叉树表示的路灯，字符由'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;
}
查看12道真题和解析