BFS Solution with no backtraking


  • 1
    M
    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;
        }
    };

  • 0
    T

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


Log in to reply
 

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