BFS Solution with no backtraking

• ``````class node{
public:
string parent;
char itself;
int id;
int height;
node(string parent_ = "",char itself_ = ' ',int id_ = -1,int height_ = -1):parent(parent_), itself(itself_),id(id_), height(height_){

}
};
int str2integer(string str, char tmp){
str = str + tmp;
int ret = 0;
int len = str.length();
for(int i = 0; i < len; ++i){
ret = (ret << 1) | (str[i] - '0');
}
return ret;
}
class Solution {
public:
vector<int> grayCode(int n) {
if(n == 0){
return vector<int>(1,0);
}
queue<node> bfs_queue;
node left_node("", '0', 0, 1);
node right_node("", '1', 1, 1);
vector<int> ret;
bfs_queue.push(left_node);
bfs_queue.push(right_node);
while(!bfs_queue.empty()){
const node &tmp_node = bfs_queue.front();
if(tmp_node.height == n){
ret.push_back(str2integer(tmp_node.parent, tmp_node.itself));
}
else{
int height = tmp_node.height;
string parent = tmp_node.parent + tmp_node.itself;
int parent_id = tmp_node.id;
if(parent_id == 0){
bfs_queue.push(node(parent, '0', 0, height + 1));
bfs_queue.push(node(parent, '1', 1, height + 1));
}
else{
bfs_queue.push(node(parent, '1', 0, height + 1));
bfs_queue.push(node(parent, '0', 1, height + 1));
}
}
bfs_queue.pop();
}
return ret;
}
};``````

• That's a really nice one, can you explain a little around the idea. How/why does this give the correct ordering of leaf nodes in the queue. I can see there's some flippety going on (`id`).

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.